one-pass algorithm to compute sample variance

In many situations it is desirable to calculate,in one iteration, the sample variance of many numbers, and withouthaving to have every number availablein computer memory before beginning processing.

Let $x_1,x_2,\mathrm{\dots }$ denote the data.The naïve formula for calculating the samplevariance in one pass,

$$v=\frac{1}{n-1}\sum _{i=1}^n{(x_i-\overline{x})}^2=\frac{\left({\sum }_{i=1}^n{x}_i^2\right)-n{\overline{x}}^2}{n-1},\overline{x}=\frac{1}{n}\sum _{i=1}^n{x}_i,$$

suffers from computational round-off error.If the mean $\overline{x}$ is large in absolute value,and ${\sum }_{i=1}^n{x}_i^2$ is close to $n{\overline{x}}^2$,then the subtraction at the end will tend to losesignificant digits on the result.Also, in rare cases, the sum of squares ${\sum }_{i=1}^n{x}_i^2$can overflow on a computer.

A better alternative, though requiring more work per iteration,is to calculate the running sample meanand variance instead,and update these as each datum is processed.Here we give the derivation of the one-pass algorithm — whichinvolves nothing more than simple algebraic manipulations.

Define the running arithmetic meanand the sum of squared residuals:

$$a_n=\frac{1}{n}\sum _{i=1}^n{x}_i,s_n=\sum _{i=1}^n{(x_i-a_n)}^2.$$

We want to express $a_{n+1}$ and $s_{n+1}$in terms of the old values $a_n$ and $s_n$.

For convenience, let $\delta =x_{n+1}-a_n$and $\gamma =a_{n+1}-a_n$.Then we have

$$a_{n+1}=\frac{n{a}_n+x_{n+1}}{n+1}=\frac{(n+1)a_n+x_{n+1}-a_n}{n+1}=a_n+\frac{\delta }{n+1}.$$

For the variance calculation,we have

$s_{n+1}$$={\displaystyle \sum _{i=1}^n}{\left((x_i-a_n)-\gamma \right)}^2+{(x_{n+1}-a_{n+1})}^2$

$={\displaystyle \sum _{i=1}^n}{(x_i-a_n)}^2-2\gamma {\displaystyle \sum _{i=1}^n}(x_i-a_n)+{\displaystyle \sum _{i=1}^n}{\gamma }^2+{(x_{n+1}-a_{n+1})}^2$

$=s_n+0+n{\gamma }^2+{(x_{n+1}-a_{n+1})}^2.$

Now observe:

$\gamma ={\displaystyle \frac{\delta }{n+1}},x_{n+1}-a_{n+1}=\delta -\gamma =(n+1)\gamma -\gamma =n\gamma ;$

hence we obtain:

$s_{n+1}=s_n+n{\gamma }^2+n^2{\gamma }^2=s_n+n(n+1){\gamma }^2$$=s_n+n\gamma \delta$

$=s_n+(x_{n+1}-a_{n+1})\delta .$

Note that the number to be added to $s_n$ is never negative,so no cancellation error will occur from this procedure.(However, there can still be computational round-off error if $s_{n+1}-s_n$happens to be very small compared to $s_n$.)

The recurrence relation for thesample covariance of two lists of numbers $x_1,x_2,\mathrm{\dots }$and $y_1,y_2,\mathrm{\dots }$can be derived similarly.If $a_n$ and $b_n$ denote the arithmetic meansof first $n$ numbers of each of the two lists respectively,then the sum of adjusted products

$$c_n=\sum _{i=1}^n(x_i-a_n)(y_i-b_n)$$

can be incrementally updated by

$$c_{n+1}=c_n+(y_{n+1}-b_{n+1})(x_{n+1}-a_n)=c_n+(x_{n+1}-a_{n+1})(y_{n+1}-b_n).$$