A kitchen scale reads a bag of flour four times a second. Each reading is the true weight plus a random error, and the error's variance (the mean square of the error) is r g². The weight itself does not change while the bag sits there. The scale's chip keeps two numbers: its current estimate x of the weight and the variance p of that estimate (how unsure it is: a standard deviation of sqrt(p) grams).
Before the first reading it starts from a guess x0 with variance p0 (the bag says 500 g, give or take 5 g, so x0 = 500, p0 = 25). For every reading z, in order, it runs the Kalman update:
K = p / (p + r) the gain: how far to move towards the reading (0 to 1)
x = x + K * (z - x) move the estimate part of the way to the reading
p = (1 - K) * p the estimate is now more certain
There is no prediction step to speak of: the weight is constant, so the estimate and its variance carry over unchanged from one reading to the next.
Write weigh(readings, x0, p0, r) that returns a pair: the list of estimates x after each reading, and the final variance p.
Examples
Input: readings = [502, 498, 505, 499], x0 = 500, p0 = 25, r = 16
Output: ([501.219512195122, 500.0, 501.3736263736264, 500.86206896551727], 3.4482758620689657)
Explanation: the first gain is 25 / (25 + 16) = 0.61, so the estimate moves 61 % of the way from
500 to 502; the variance falls to 9.76 and the next gain is only 0.38.
Input: readings = [], x0 = 250, p0 = 4, r = 1
Output: ([], 4)
Press Run with plot(readings, kind="scatter") and plot(weigh(readings, 500, 25, 16)[0]) to watch the estimate calm down.
Constraints
- answers are compared with a tolerance of
1e-6
Goals
- Run the update step of a one-number Kalman filter: gain, new estimate, new variance
- See the gain shrink as the estimate's variance falls with every reading
- Recognise that a filter that starts knowing nothing reproduces the running mean