A one-pass variance computes the mean of squares minus the square of the mean. Over 1 million prices near 40000 with a true standard deviation of 0.01 it returns a negative number. Show the cancellation with the magnitudes involved and give the algorithm that fixes it.

A one-pass variance computes the mean of squares minus the square of the mean. Over 1 million prices near 40000 with a true standard deviation of 0.01 it returns a negative number. Show the cancellation with the magnitudes involved and give the algorithm that fixes it.

Approach: Compare the magnitude of the two terms being subtracted against the magnitude of their difference, and count how many significant digits survive the subtraction in double precision.

Both terms are about 1.6e9 while their difference is 1e-4, so roughly 13 of the 16 significant digits cancel and only rounding noise remains, which is catastrophic cancellation and is why the result can come out negative; the Welford algorithm fixes it by updating the mean and the sum of squared deviations from that running mean, so the large intermediate is never formed. A double resolves 1.6e9 to about 4e-7 in absolute terms while the wanted answer is 1e-4, so the subtraction leaves three correct digits at best and often none once each term carries its own accumulated error. Subtracting a shift such as the first observation before accumulating recovers most of the accuracy for one extra subtraction per sample, since variance has shift invariance. Welford costs one extra multiply per sample against the naive form and stays stable for any mean magnitude.

Follow-up: How do you merge two Welford accumulators computed on separate threads without losing that stability?

Key concepts: catastrophic cancellation, significant digits, welford algorithm, shift invariance.