How to Learn Welford’s Online Algorithm: Running Mean, Stable Variance, One-Pass Updates and Streaming Statistics

Wait, What?

You can calculate a reliable mean and variance for a stream without storing the stream.

That sounds almost too convenient. Variance appears to require knowing how far every observation lies from the final mean, yet the final mean is not known until the data has arrived. Welford’s online algorithm resolves this by maintaining a small state that is updated after each new value. The result is a one-pass method that is much more numerically stable than the tempting formula based on E[x²] − E[x]².

For learners, Welford is a compact doorway into streaming algorithms, recurrence relations, invariants, floating-point stability, sufficient statistics and mergeable computation. For professionals, it is a reminder that mathematically equivalent formulas can behave very differently on real hardware.

Quick Answer

Learn Welford in this order: mean → deviation from the old mean → updated mean → deviation from the new mean → accumulated M2 → sample/population variance → numerical stability → mergeable summaries → edge cases and tests. Do not begin by memorising the code. First understand why the product of the two deviations updates the sum of squared deviations correctly.

1. The Streaming Problem

Suppose values arrive one at a time:

x1, x2, x3, ...

You want the count, mean and variance at any moment, but you do not want to keep every value. A batch algorithm can store the data, compute the mean, then make a second pass to compute squared deviations. A stream may be too large, too fast, or unbounded.

The algorithmic question is therefore: what small state contains everything needed to update the statistics when the next observation arrives?

2. The Running Mean Is the First Recurrence

Let n be the number of observations already incorporated and mean their mean. A new value x arrives. Define:

delta = x - mean
n = n + 1
mean = mean + delta / n

This formula says: move the old mean toward the new observation by one n-th of the gap. The more data you already have, the less one new observation moves the mean.

3. Variance Needs One More State: M2

Welford’s method usually maintains M2, the accumulated sum of squared deviations from the current mean:

M2 = Σ (xi - mean)^2

The subtlety is that when the mean changes, the deviations of all earlier observations change too. Welford’s recurrence accounts for that without revisiting them.

4. The Core Update

n = 0
mean = 0
M2 = 0

for each x:
    n += 1
    delta = x - mean
    mean += delta / n
    delta2 = x - mean
    M2 += delta * delta2

After the update:

• population variance = M2 / n when n > 0
• sample variance = M2 / (n - 1) when n > 1

The two deviations are deliberately different. delta uses the old mean. delta2 uses the new mean. Their product gives exactly the increment needed for the corrected sum of squares.

5. Trace a Tiny Example

Use the stream 10, 12, 14.

After 10: n=1, mean=10, M2=0.

After 12: delta=2, new mean =11, delta2=1, so M2=2.

After 14: delta=3, new mean =12, delta2=2, so M2=2+6=8.

Population variance is 8/3. Sample variance is 8/2 = 4. The important learning move is to trace old mean → delta → new mean → delta2 → M2 for every observation.

6. Why the Naive One-Pass Formula Is Dangerous

A mathematically valid identity is:

variance = mean(x^2) - mean(x)^2

On a computer, this can be numerically fragile when both terms are large and their difference is small. Subtracting nearly equal floating-point numbers can lose significant digits through cancellation. A dataset such as values near one billion with only tiny variation is a classic stress case.

Welford’s recurrence works with deviations around the evolving mean rather than subtracting two huge nearly equal quantities at the end. That does not make floating-point arithmetic exact, but it generally gives much better numerical behaviour.

7. Mathematical Equivalence Is Not Computational Equivalence

This is the deeper lesson. Two formulas can be identical over real numbers yet have different error behaviour under finite-precision arithmetic. Algorithm design therefore includes the representation model, not just algebra.

IEEE 754 floating-point arithmetic defines how modern systems represent and round floating-point values. Professional numerical code must reason about roundoff, cancellation, overflow, underflow, exceptional values and the order in which operations occur.

8. The Invariant to Hold in Your Head

After processing exactly n observations:

• mean is the mean of those n observations.
• M2 is their corrected sum of squared deviations from that mean.

Every update must preserve those two claims. Thinking in invariants is stronger than remembering syntax because it lets you re-derive the method in another language or representation.

9. Sample Variance and Population Variance Are Different Questions

Do not turn M2 into “variance” without stating the denominator. If the observations are the entire population of interest, divide by n. If they are a sample used to estimate an underlying population variance under the usual assumptions, divide by n-1.

For n=0, neither mean nor variance is meaningfully defined. For n=1, population variance is zero for that one-element population, while sample variance is undefined because the denominator would be zero.

10. Streams Can Be Combined

A professional implementation often processes partitions independently and merges their summaries. Suppose group A has nA, meanA, M2A and group B has nB, meanB, M2B. Let:

delta = meanB - meanA
n = nA + nB
mean = meanA + delta * nB / n
M2 = M2A + M2B + delta*delta * nA*nB / n

This makes the state useful for parallel processing, distributed aggregation, chunked files and map-reduce style pipelines. The exact evaluation order still matters for floating-point reproducibility, but you no longer need the raw samples to combine partitions.

11. A Python-Like Implementation

class RunningStats:
    def __init__(self):
        self.n = 0
        self.mean = 0.0
        self.M2 = 0.0

    def add(self, x):
        self.n += 1
        delta = x - self.mean
        self.mean += delta / self.n
        delta2 = x - self.mean
        self.M2 += delta * delta2

    def population_variance(self):
        return self.M2 / self.n if self.n else None

    def sample_variance(self):
        return self.M2 / (self.n - 1) if self.n > 1 else None

Production code should also decide how to handle NaN, infinities, missing data, decimal or fixed-point requirements, integer-to-float conversion and thread safety.

12. Testing Should Attack Numerical Weaknesses

Do not test only tidy values such as 1,2,3,4. Include:

• all-equal values
• very large offsets with tiny spread
• mixed positive and negative values
• one observation and empty input
• long streams
• partitions merged in different groupings
• NaN and infinity policies if your application permits them

Cross-check against a high-quality two-pass reference calculation using higher precision where practical.

13. What Welford Does Not Solve

It does not automatically solve robust statistics, quantiles, heavy tails, missing-data modelling, concept drift, windowed statistics or adversarial numerical conditioning. Weighted observations and covariance require extensions. Sliding windows are especially different because removing an old observation is not the same operation as adding a new one.

14. Where Professionals Use This Pattern

The same compact-state idea appears in telemetry, sensor processing, online monitoring, experimentation systems, simulation, scientific computing, anomaly detection and machine-learning feature statistics. The transferable idea is not merely “how to compute variance”; it is how to turn a batch quantity into an updateable state with a preserved invariant.

15. Common Failure States

• Using mean(x²)-mean(x)² without considering cancellation.
• Updating mean before saving the old-mean deviation.
• Using the same delta twice instead of old-mean and new-mean deviations.
• Confusing M2 with variance.
• Dividing sample variance by n.
• Ignoring empty and one-element cases.
• Assuming merge order gives bit-for-bit identical floating-point results.
• Calling the method “exact” because it is stable.

16. Practice Ladder: Beginner to Professional

• Beginner: update the running mean by hand for five values.
• Foundation: trace n, mean, delta, delta2, M2 in a table.
• Intermediate: derive the recurrence from the corrected sum of squares and implement it without copying.
• Advanced: compare Welford against the naive one-pass formula on large-offset, small-variance data.
• Professional: implement mergeable accumulators, specify exceptional-value policy, test partition-order sensitivity and document sample-versus-population semantics.
• Transfer: identify another batch calculation that might be rewritten as an online invariant-preserving update.

17. A Better Way to Study the Algorithm

Programming-education research repeatedly supports making learners read, trace, predict and explain working code before asking them to produce a complete solution. For Welford, use a state table and predict the next mean and M2 before running the program. Then deliberately break one update line and explain which invariant fails. This turns a short formula into a durable mental model.

Learning Hall Boundary

This article owns Welford’s online mean/variance recurrence and its numerical-stability lessons. It does not replace the existing compensated-summation article, sketching/quantile articles, broader statistics instruction, MindOS learning-process material, Bolt calibration work or Student/Studying Interface jobs.

Evidence Boundary

The foundational source is B. P. Welford, “Note on a Method for Calculating Corrected Sums of Squares and Products,” Technometrics 4(3), 1962, pp. 419–420: DOI record. Floating-point behaviour should be interpreted under the current IEEE 754-2019 standard: IEEE 754-2019. The teaching design also draws on computing-education evidence favouring code reading, prediction, tracing and structured progression before independent construction, including PRIMM guidance from the Raspberry Pi Computing Education Research Centre.

Professional rule: you understand Welford when you can explain the invariant, derive the update, distinguish sample from population variance, and show why a mathematically equivalent formula can be numerically worse.