How Far to Trust the Cellar Thermometer

A wine cellar's controller estimates the air temperature from a cheap thermometer, once a minute. Two numbers describe its world:

• q (°C²): the process noise, how much the true temperature may wander in one minute (the variance of that change). A large q says "my model of the cellar is poor; the temperature can move".
• r (°C²): the measurement noise, the variance of the thermometer's error. A large r says "the sensor is poor".

Each minute the filter's variance p goes through two steps:

p = p + q                 predict: a minute has passed, so the estimate is less certain
K = p / (p + r)           the gain used on this minute's reading
p = (1 - K) * p           update: the reading made it more certain again

The readings themselves never enter these lines, so the whole sequence of gains can be worked out in advance. After a while the gain settles to a steady-state value. With m = (q + sqrt(q*q + 4*q*r)) / 2 (the predicted variance at steady state), it is m / (m + r).

Write trust(q, r, p0, n) that starts from p = p0 and returns a pair: the list of the first n gains, and the steady-state gain.

Examples

Input:  q = 0.01, r = 0.04, p0 = 1.0, n = 5
Output: ([0.9619047619047618, 0.5479009687836388, 0.4437958389462656, 0.409610074008616, 0.3974488250817834], 0.3903882032022076)
Explanation: the first prediction makes p = 1.01, so K = 1.01 / 1.05 = 0.962. The gains fall towards 0.39:
in the long run each reading moves the estimate 39 % of the way.

Input:  q = 0.04, r = 0.01, p0 = 1.0, n = 5
Output: ([0.9904761904761905, 0.8330683624801271, 0.8285636413191605, 0.8284311433247603, 0.8284272430420166], 0.8284271247461901)
Explanation: the same two numbers swapped: now the sensor is the better source and the gain stays high.

Input:  q = 0, r = 0.04, p0 = 1.0, n = 3
Output: ([0.9615384615384615, 0.49019607843137303, 0.32894736842105293], 0.0)
Explanation: with no process noise the gain keeps falling towards 0: a filter that believes nothing
changes eventually stops listening.

Constraints

• answers are compared with a tolerance of 1e-6

Goals

• Run the variance part of a Kalman filter on its own: predict, gain, update
• See that the gain depends only on the two noise variances, not on the readings
• Compute the steady-state gain and read it as a balance between trusting the model and trusting the sensor