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

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Moving average and low-pass filters explained

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.

The noise left in an average, as a share of one reading's noise, against the seconds spent taking readings01020304000.250.50.751seconds spent taking readings, one every 0.1 snoise left, x sigma1 reading4 readings, 0.3 s: half the noise100 readings, 9.9 s: a tenth400 readings,39.9 s: a twentiethhalving it again costs30 s more
Diminishing returns. The first halving of the noise takes 0.3 s; halving it again from 100 readings to 400 takes 30 s. Almost all the gain comes in the first few seconds, and the curve is nearly flat after that.
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 between one reading and the next, and 20 cm while taking ten. 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.

Sixty readings taken while driving at 20 cm/s are spread over more than a metre of the robot's pathwall60 readings, one every 2 cm: 118 cm of drivingthe average is the gap from herethe robotis now hereat 20 cm/s, the average is 59 cm out of date
Averaging 60 readings at 20 cm/s. Each tick is one reading, 2 cm further on than the last. Their mean is the gap from the middle of the stretch, 59 cm behind where the robot is by the time it has finished.

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). Good to a centimetre at one sigma still leaves a third of answers further out than that, so take enough readings that a centimetre is two sigma.

from bugbot import *
connect()

# how many readings put two sigma at 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?