Guessing a number from noisy readings
Tonight's idea
A sensor measures a hidden number \(x\), but each reading has a random error. The model: \(y_k = x + e_k\), with errors that are independent, average zero, and share one standard deviation \(\sigma\), the "spread".
The natural guess after \(n\) readings is their average, \(g_n\). You need not store the readings. Keep only the guess and the count, and update:
\(g_n = g_{n-1} + \dfrac{1}{n}\,(y_n - g_{n-1})\), starting from \(g_1 = y_1\).
The bracket is the surprise: how far the new reading lands from your guess. The fraction \(1/n\) is the gain: how much of the surprise you believe. Early on you believe a lot; later, little.
Why trust the guess more as time passes? For independent errors, variances add, and \(\mathrm{Var}(aY) = a^2\,\mathrm{Var}(Y)\). So the average has variance \(n\sigma^2/n^2 = \sigma^2/n\), and spread \(\sigma/\sqrt{n}\).
Guess, compare, correct by a gain: that loop is the core of the Kalman filter (1960), which helped navigate Apollo. Steering a system on such guesses is stochastic control.
Watch one: five readings, one number kept
Made-up readings: 52, 47, 50, 55, 46. Each row needs only the row above and the new reading.
| \(n\) | reading \(y_n\) | surprise \(y_n - g_{n-1}\) | gain \(1/n\) | new guess \(g_n\) |
|---|---|---|---|---|
| 1 | 52 | 52 | ||
| 2 | 47 | \(-5\) | 1/2 | \(52 - 2.5 = 49.5\) |
| 3 | 50 | \(0.5\) | 1/3 | \(49.5 + 0.167 = 49.67\) |
| 4 | 55 | \(5.33\) | 1/4 | \(49.67 + 1.33 = 51\) |
| 5 | 46 | \(-5\) | 1/5 | \(51 - 1 = 50\) |
Check: the readings sum to 250 and \(250/5 = 50\), the ordinary average exactly (49.67 is \(149/3\), rounded for display). The last two surprises are similar in size, but the later one moves the guess less: smaller gain.
Your turn
- (a) A sixth reading, 53, arrives. Update \(g_5 = 50\) with the rule, then check against the average of all six readings. (b) Show it always works: if \(g_{n-1}\) is the average of the first \(n-1\) readings, then the rule makes \(g_n\) the average of the first \(n\).
- In the model, suppose one reading has spread \(\sigma = 4\). (a) Find the spread of the average of 4, 16 and 64 readings. (b) You have 5 readings. How many readings in total would halve the spread of your average? (c) Your sensor always reads 1 too high. Which assumption of the model fails, and does averaging more readings fix it?
- Now the hidden number moves. Made-up readings: 48, 52, 50, 62, 58, 60 (the hidden number jumped from 50 to 60 after the third reading). Starting from \(g_1 = 48\), track them twice: (a) with the running average, gain \(1/n\); (b) with a fixed gain of \(\tfrac12\), that is \(g_n = g_{n-1} + \tfrac12 (y_n - g_{n-1})\). Which ends nearer 60, and why?
- With fixed gain \(\tfrac12\) and a long run of readings behind it, the guess is very nearly \[g = \tfrac12 y_n + \tfrac14 y_{n-1} + \tfrac18 y_{n-2} + \cdots\] (a) What do the weights add up to? (b) Suppose the hidden number stays put and the model holds. Show that \(\mathrm{Var}(g) = \sigma^2/3\). (c) How many readings does the running average need to match that? What does the fixed gain give you in exchange for never improving?
Stretch: two thermometers
Two thermometers read the same room: 20.0 and 21.0. Their errors are independent and average zero, with spreads 1 and 2. Guess \(g = w \cdot 20.0 + (1-w) \cdot 21.0\). Write \(\mathrm{Var}(g)\) in terms of \(w\), find the \(w\) that makes it smallest, and give the guess and its spread. How does the plain average 20.5 compare? Then write your guess as old guess plus gain times surprise.
Answers
- (a) Surprise \(53 - 50 = 3\), gain \(1/6\), so \(g_6 = 50.5\). Check: \(303/6 = 50.5\). (b) Write \(S\) for the sum of the first \(n-1\) readings, so \(g_{n-1} = S/(n-1)\). Then \(g_n = g_{n-1}\left(1 - \tfrac1n\right) + \tfrac{y_n}{n} = \tfrac{S}{n-1}\cdot\tfrac{n-1}{n} + \tfrac{y_n}{n} = \tfrac{S + y_n}{n}\). Since \(g_1 = y_1\) is the average of one reading, the rule gives the average at every step.
- (a) \(4/\sqrt4 = 2\), \(4/\sqrt{16} = 1\), \(4/\sqrt{64} = 0.5\). (b) The spread is \(\sigma/\sqrt n\), so halving it needs 4 times the readings: 20 in total, 15 more. (From \(4/\sqrt5 \approx 1.79\) to \(4/\sqrt{20} \approx 0.89\).) (c) "Errors average zero" fails. Averaging shrinks the random scatter, but the guess settles on \(x + 1\), not \(x\). No number of readings removes a steady bias.
- (a) 48, 50, 50, 53, 54, 55. (b) 48, 50, 50, 56, 57, 58.5. The fixed gain ends nearer 60. The running average still gives the three old readings near 50 the same weight as the new ones, and its gain has dropped to \(1/6\), so it creeps. The fixed gain keeps believing half of every surprise, so old readings fade.
- (a) \(\tfrac12 + \tfrac14 + \tfrac18 + \cdots = 1\), so \(g\) is a weighted average. (b) Variances add with squared weights: \(\sigma^2\left(\tfrac14 + \tfrac1{16} + \tfrac1{64} + \cdots\right) = \sigma^2 \cdot \dfrac{1/4}{1 - 1/4} = \dfrac{\sigma^2}{3}\). (c) \(\sigma^2/n = \sigma^2/3\) at \(n = 3\): however long it runs, the fixed-gain guess is only about as steady as an average of 3 readings, with spread \(\sigma/\sqrt3 \approx 0.58\sigma\). In exchange it forgets: a reading \(k\) steps back has weight \(1/2^{k+1}\), so it can follow a number that moves. Steady or nimble; you trade one for the other.
Stretch. \(\mathrm{Var}(g) = w^2 \cdot 1 + (1-w)^2 \cdot 4\). Its derivative \(2w - 8(1-w)\) is zero at \(w = \tfrac45\), a minimum since the quadratic opens upward. So \(g = 0.8 \cdot 20.0 + 0.2 \cdot 21.0 = 20.2\), with variance \(0.64 + 0.16 = 0.8\) and spread \(\sqrt{0.8} \approx 0.89\), better than either thermometer alone. The weights 4 to 1 are in the ratio of \(1/\text{variance}\), that is \(\tfrac11 : \tfrac14\), not \(1/\text{spread}\). The plain average 20.5 has variance \(\tfrac14 (1 + 4) = 1.25\), spread about 1.12: worse than the good thermometer on its own. As an update: \(20.2 = 20.0 + \tfrac15 (21.0 - 20.0)\), and the gain is \(\dfrac{1}{1 + 4}\), old variance over old plus new. Put in old variance \(\sigma^2/(n-1)\) and new variance \(\sigma^2\) and that gain is \(1/n\), the running average again.