mathematics//numerical methods//Welford's algorithm

Welford's algorithm is a one-pass method for computing a running mean and variance that updates both with each new sample in constant memory and constant time, and it is what a microcontroller or a PLC uses to keep statistics of a signal inside a loop: the noise level of a sensor, the spread of a vibration amplitude, the baseline a fault detector compares against. It stores three numbers, the count \(n\), the mean \(\bar x\) and a running sum of squared deviations \(M\), and with each sample \(x_n\):

Welford's algorithm is a one-pass method for computing a running mean and variance that updates both with each new sample in constant memory and constant time, and it is what a microcontroller or a PLC uses to keep statistics of a signal inside a loop: the noise level of a sensor, the spread of a vibration amplitude, the baseline a fault detector compares against. It stores three numbers, the count nnn, the mean xˉ\bar xxˉ and a running sum of squared deviations MMM, and with each sample xnx_nxn​:

δ=xn−xˉn−1,xˉn=xˉn−1+δn,Mn=Mn−1+δ (xn−xˉn),s2=Mnn−1.\delta=x_n-\bar x_{n-1},\qquad \bar x_n=\bar x_{n-1}+\frac{\delta}{n},\qquad M_n=M_{n-1}+\delta\,(x_n-\bar x_n),\qquad s^2=\frac{M_n}{n-1}.δ=xn​−xˉn−1​,xˉn​=xˉn−1​+nδ​,Mn​=Mn−1​+δ(xn​−xˉn​),s2=n−1Mn​​.

Every quantity it adds up is a deviation from the current mean, so the numbers stay the size of the noise, never the size of the signal.

That is the whole point, because the textbook shortcut Var⁡(x)=E[x2]−E[x]2\operatorname{Var}(x)=\mathbb E[x^2]-\mathbb E[x]^2Var(x)=E[x2]−E[x]2 does the opposite. A barometer reading 101,325 Pa with 1 Pa of noise makes it subtract two eleven-digit numbers to get a one-digit answer; in single precision, which keeps about seven significant digits, the result is garbage and sometimes negative (floating-point arithmetic, which names the effect catastrophic cancellation). A negative variance then flows into a square root, a threshold or a Kalman filter's RRR and the failure appears far from its cause.

It belongs wherever statistics must live inside the real-time loop. At 1 kHz on a microcontroller there is no room to store a window and recompute; Welford's update costs a few operations per sample and never grows. Batch computations (bootstrap, MCMC, a full refit) run offline on a PC or in the cloud instead.

Its sample count only grows, so a plain Welford accumulator describes everything since reset with equal weight. A detector that must follow a slowly changing baseline either resets it periodically or uses an exponentially weighted version, which forgets old samples at a chosen rate (EWMA).

Two accumulators can be merged exactly (counts, means and MMM combine with a short formula), which is how statistics computed separately on several cores, devices or days are pooled without revisiting the raw data.

The variance it returns is the sample variance with n−1n-1n−1 (variance); with correlated samples, as a sensor at a high rate always produces, the count nnn overstates how much information that variance contains (effective sample size).