Averaging

The square root of n, why it stops paying, and what it costs in time.

U4.2Noise and filteringUniversity25 min

Do this lesson in the simulator

The cheapest filter is the mean of n independent readings, and the arithmetic of how much it buys is worth knowing exactly.

The square root of n

Averaging n independent readings, each with standard deviation sigma, gives an estimate with standard deviation

sigma / sqrt(n)

Four readings halve the noise. A hundred divide it by ten. Ten thousand divide it by a hundred.

Look at those numbers and the bad news is already visible: diminishing returns. Going from 1 to 4 readings buys a factor of 2 and costs 0.3 seconds. Going from 100 to 400 buys another factor of 2 and costs 30 seconds. Past a certain point the noise stops being what limits you, and the bias, which averaging does nothing about, is all that is left.

from bugbot import *
connect()

SIGMA = 4.0
for n in (1, 4, 16, 64, 256):
    print(n, "readings ->", round(SIGMA / n ** 0.5, 2), "cm, taking", round(n * 0.1, 1), "s")

Run this in the simulator

The cost is time

That last column is the whole engineering problem. A robot driving at 20 cm/s moves 2 cm while taking ten readings. Average sixty readings and the robot has travelled more than a metre, and the "average distance to the wall" you computed is the average over a metre of driving, which is not a measurement of anything useful.

So: average while still, filter while moving. The first half of this module is about the still case; the second half is about what to do when you cannot stop.

Independence, again

Averaging only divides the noise by root n if the readings are independent. Two things break that:

  • Reading faster than the sensor updates. The same sample counted twice adds nothing and makes your estimate of the improvement wrong.
  • Correlated noise. If something in the environment is nudging every reading the same way over the averaging window, that shift is not averaged out at all. It is bias for as long as it lasts.

Task: average it down

The sensor has about 4 cm of noise on it. Standing still, produce an estimate of the gap to the wall good to about a centimetre, and print readings: (how many you took) and distance: (your answer).

from bugbot import *
connect()

# how many readings do you need for 1 cm, with sigma = 4?

Challenges

  1. Work out the number of readings you need before you write the loop, then check it.
  2. Average 16 readings ten separate times and look at the spread of the ten answers. Is it sigma over 4?
  3. At set_noise(0, depth=8), how long would an estimate good to 1 cm take? Is that a practical robot?