DEV Community

Kyle Pena
Kyle Pena

Posted on Edited on

Derivation of Welford's Algorithm

#statistics #algorithms #datascience

This will be somewhat out of context if you're coming here first. It's really a footnote in a much longer series of blog posts on summarizing data distributions in computing environments where storage is at a premium.

In that blog post, I wanted to explain how to derive Welford's Algorithm for the recurrence relation for the second central moment, and found the explanations I could find a little lacking (at least for me).

I found this helpful post to be a great starting point, but the algebra part of the post skipped over so many steps that I couldn't follow it.

So I worked it out in greater detail. I'm hoping this is helpful to other mere mortals who, like myself, couldn't quite connect the dots.

Notation:

  • y represents a new observation.
  • μ' is the updated mean (the mean after incorporating y).
  • M2M_2 is the second central moment - well, not quite. Technically you'd have to divide by N to get the central moment. But we'll call it the central moment here.
  • N is the number of observations including y.

First, some work on the mean update formula:

μ′=μ+y−μN\mu^\prime = \mu + \frac{y - \mu}{N}
Nμ′=Nμ+y−μN\mu^\prime = N\mu + y - \mu
(N−1)μ′+μ′=(N−1)μ+y(N-1)\mu^\prime + \mu^\prime = (N-1)\mu + y
(N−1)μ′−(N−1)μ=y−μ′(N-1)\mu^\prime - (N-1)\mu = y - \mu^\prime
(N−1)μ−(N−1)μ′=μ′−y(N-1)\mu - (N-1)\mu^\prime = \mu^\prime - y

Now, the main derivation:

M2′−M2=∑1N(yi−μ′)2−∑1N−1(yi−μ)2M_2^\prime - M_2 = \sum_1^N{(y_i - \mu^\prime)^2} - \sum_1^{N-1}{(y_i - \mu)^2}
=(y−μ′)2+∑1N−1(yi−μ′)2−(yi−μ)2= (y - \mu^\prime)^2 + \sum_1^{N-1}{(y_i - \mu^\prime)^2 - (y_i - \mu)^2}
=(y−μ′)2+∑1N−1(yi2−2yiμ′+μ′2)−(yi2−2yiμ+μ2)= (y - \mu^\prime)^2 + \sum_1^{N-1}{(y_i^2 - 2y_i\mu^\prime +\mu^{\prime 2}) - (y_i^2 - 2y_i\mu + \mu^2)}
=(y−μ′)2+∑1N−1−2yiμ′+2yiμ+(μ′2−μ2))= (y - \mu^\prime)^2 + \sum_1^{N-1}{-2y_i\mu^\prime + 2y_i\mu + (\mu^{\prime 2} - \mu^2))}
=(y−μ′)2+∑1N−1−2yi(μ′−μ)+(μ′−μ)(μ′+μ)= (y - \mu^\prime)^2 + \sum_1^{N-1}{-2y_i(\mu^\prime - \mu) + (\mu^\prime - \mu)(\mu^\prime + \mu)}
=(y−μ′)2+∑1N−1(μ′−μ)(−2yi+μ′+μ)= (y - \mu^\prime)^2 + \sum_1^{N-1}{(\mu^\prime - \mu)(-2y_i + \mu^\prime + \mu)}
=(y−μ′)2+(μ−μ′)∑1N−1(2yi−μ′−μ)= (y - \mu^\prime)^2 + (\mu - \mu^\prime) \sum_1^{N-1}{(2y_i - \mu^\prime - \mu)}
=(y−μ′)2+(μ−μ′)[2(N−1)μ−(N−1)μ′−(N−1)μ]= (y - \mu^\prime)^2 + (\mu - \mu^\prime) [ 2(N-1)\mu - (N-1)\mu^\prime - (N-1)\mu ]
=(y−μ′)2+(μ−μ′)[(N−1)μ−(N−1)μ′]= (y - \mu^\prime)^2 + (\mu - \mu^\prime) [ (N-1)\mu - (N-1)\mu^\prime ]

Substitute the mean update term we worked out earlier.

=(y−μ′)2+(μ−μ′)(μ′−y)= (y - \mu^\prime)^2 + (\mu - \mu^\prime) (\mu^\prime - y)
=(y−μ′)2+(μ′−μ)(y−μ′)= (y - \mu^\prime)^2 + (\mu^\prime - \mu) (y - \mu^\prime)
=(y−μ′)(y−μ′+μ′−μ)= (y - \mu^\prime)(y - \mu^\prime + \mu^\prime - \mu)
=(y−μ′)(y−μ)= (y - \mu^\prime)(y - \mu)

This equals the difference M2′−M2M_2^\prime - M_2 , and so the complete recurrence relation for the second central moments is:

M2′=M2+(y−μ′)(y−μ)M_2^\prime = M_2 + (y - \mu^\prime)(y - \mu)

And thus the recurrence relation for the corrected sample variance based on the second central moment is:

σ′2=1N−1[M2+(y−μ′)(y−μ)]\sigma^{\prime 2} = \frac{1}{N-1} [ M_2 + (y - \mu^\prime)(y - \mu) ]

Top comments (0)