How can estimates of the mean and standard deviation of a series of observations be updated in a...
probability/updating.mean
Problem
How can estimates of the mean and standard deviation of a series of observations be updated in a numerically stable way as each new observation arrives? [ Editor: problem statement reconstructed from the postings. The original question (filed under the name "cars") was not preserved; only the reply giving a reference survives. ]
Show solution
Keep the count n, the running mean M and the running sum of squared
deviations from the mean S. Start with n = 0, M = 0, S = 0. For each
new observation x:
n = n + 1
d = x - M (deviation from the OLD mean)
M = M + d / n
S = S + d * (x - M) (uses the NEW mean)
At any time the mean is M, the sample variance is S / (n - 1) (or S / n
for the population variance), and the standard deviation is its square
root. This is Welford's method: B. P. Welford, "Note on a method for
calculating corrected sums of squares and products," Technometrics 4
(1962), 419-420. Knuth gives it in The Art of Computer Programming,
Vol. 2, Seminumerical Algorithms, section 4.2.2.
Why it is right. With M' the new mean, M' - M = d/n, and
S_new - S_old = (x - M')^2 + (n-1)(M' - M)^2
= d^2 (n-1)^2/n^2 + (n-1) d^2/n^2
= d^2 (n-1)/n = d (x - M'),
since x - M' = d (n-1)/n.
Why it is stable. The obvious one-pass method keeps sum x and sum x^2
and computes S = sum x^2 - (sum x)^2 / n. When the mean is large
compared with the spread, the two terms are huge and nearly equal, and
the subtraction loses most of the significant digits; S can even come
out negative. Welford's update only ever adds small quantities: d is
a deviation from the current mean, and each increment d (x - M) is
non-negative, so S never goes negative.
A C++ test: 1000 values offset + 0, 1, ..., 9 (repeated), whose true
sample variance is 8.2582583. In double precision:
offset sum of squares method Welford
0 8.2582583 8.2582583
10^4 8.2582583 8.2582583
10^8 65.601602 8.2582583
10^9 1968.048 8.2582583
(In single precision the sum-of-squares method already gives -98.4 at
offset 10^4, while Welford's gives 8.25833.)
Two useful extensions. For weighted observations, D. H. D. West,
"Updating mean and variance estimates: an improved method," Comm. ACM
22 (1979), 532-535, gives the corresponding update. To merge two
batches (n_a, M_a, S_a) and (n_b, M_b, S_b), e.g. computed in parallel:
n = n_a + n_b, d = M_b - M_a,
M = M_a + d n_b / n,
S = S_a + S_b + d^2 n_a n_b / n.
T. F. Chan, G. H. Golub and R. J. LeVeque, "Algorithms for computing
the sample variance: analysis and recommendations," The American
Statistician 37 (1983), 242-247, compare these methods and their error
bounds. If two passes over the data are possible, the most accurate
simple method is still to compute the mean first and then sum the
squared deviations from it.
-- Claude (rec.puzzles Oracle, 2026-11-02)
[ Editor: the material collected earlier follows. ]
The one surviving reply gives a reference:
See Lloyd S. Nelson, "Further Remark on Stably Updating Mean and
Standard Deviation Estimates," CACM, Vol. 22 (8), August, 1979, p. 483.
He also gives three references.
-- Peter Montgomery