Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We've learned this algorithm in class but I'm not sure I've fully understood the correctness of this approach.

It is known as Welford's algorithm for the sum of squares, as described in: Welford, B.P., "Note on a Method for Calculating Corrected Sums of Squares and Products", Technometrics, Vol. 4, No. 3 (Aug., 1962), pp. 419-420

The two-pass algorithm to estimate the sample deviation is simple. We first estimate the mean by one pass and then calculate the standard deviation. In short, it is $s_n^2 = \frac{1}{n-1} \sum_{i=1}^n (Y_i - \hat{Y})^2$.

The one-pass approach has three steps.

1) $v_1 = 0$

2) $v_k = v_{k-1} + \frac{1}{k(k-1)} (\sum_{i=1}^{k-1} Y_i - (k-1) Y_k)^2 (2 \leq k \leq n)$

3) $s_n^2 = \frac{v_n}{n-1}$.

Can someone help me understand how this approach works?

share|cite|improve this question
This isn't quite "one-pass" because step (2) contains a sum from $i=1$ to $k-1$. Better to say something like $m_1 = Y_1$, $m_k = m_{k-1} + Y_k$, $v_k = v_{k-1} + \frac{1}{k(k-1)} (m_{k-1} - (k-1)Y_k)^2$ – Robert Israel Feb 29 '12 at 22:17

$v_n$ is going to be $\sum_{i=1}^n (Y_i - \overline{Y}_n)^2$ where $\overline{Y}_n = \frac{1}{n} \sum_{i=1}^n Y_i$. Note that by expanding out the square, $v_n = \sum_{i=1}^n Y_i^2 - \frac{1}{n} \left(\sum_{i=1}^n Y_i\right)^2$. In terms of $m_k = \sum_{i=1}^k Y_i$, we have $$v_n = \sum_{i=1}^n Y_i^2 - \frac{1}{n} m_n^2 = \sum_{i=1}^{n-1} Y_i^2 + Y_n^2 - \frac{1}{n} (m_{n-1} + Y_n)^2$$ On the other hand, $$v_{n-1} = \sum_{i=1}^{n-1} Y_i^2 - \frac{1}{n-1} m_{n-1}^2$$ Since $(m_{n-1} + Y_n)^2 = m_{n-1}^2 + 2 Y_n m_{n-1} + Y_n^2$, the difference between these is $$ v_n - v_{n-1} = \left(1 - \frac{1}{n}\right) Y_n^2 + \left(\frac{1}{n-1} - \frac{1}{n}\right) m_{n-1}^2 - \frac{2}{n} Y_n m_{n-1} $$ $$ = \frac{1}{n(n-1)} m_{n-1}^2 - \frac{2}{n} Y_n m_{n-1} +\frac{n-1}{n} Y_n^2 $$ $$ = \frac{1}{n(n-1)} \left(m_{n-1} - (n-1) Y_n\right)^2 $$

share|cite|improve this answer
If I understand this correctly, one initializes $m_0 = v_0 = v_1 = 0$. One would then begin calculating $m_n$ from the first value ($n=1$), but wait to begin calculation of $v_n$ until the second value ($n=2$). $v_1 = (Y_1-\bar{Y_1})^2$ evaluates to zero; however, if, at the first value in the series ($n=1$), one uses the recursive relation, $v_1=v_0+\frac{1}{n(n-1)}\left(m_{n-1}-(n-1)Y_n\right)^2$, the expression diverges due to the $\frac{1}{n-1}$ term. Therefore, the recursive relation for $v_n$ should be delayed until the second value in the series. – user001 Nov 1 '12 at 11:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.