PlanetMath: one-pass algorithm to compute sample variance

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (24)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

one-pass algorithm to compute sample variance

(Algorithm)

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

Let $x_1, x_2, \dotsc$ denote the data. The naïve formula for calculating the sample variance in one pass,

$\displaystyle v = \frac{1}{n-1} \sum_{i=1}^n (x_i - \overline{x})^2 = \frac{\le... ... n\overline{x}^2}{n-1} \,, \quad \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 lose significant 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 mean and variance instead, and update these as each datum is processed. Here we give the derivation of the one-pass algorithm -- which involves nothing more than simple algebraic manipulations.

Define the running arithmetic mean and the sum of squared residuals:

$\displaystyle a_n = \frac{1}{n} \sum_{i=1}^n x_i\,, \quad 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

and

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

$\displaystyle 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

$\displaystyle s_{n+1}$	$\displaystyle = \sum_{i=1}^n \bigl( (x_i - a_n) - \gamma \bigr)^2 + (x_{n+1} - a_{n+1})^2$
	$\displaystyle = \sum_{i=1}^n (x_i - a_n)^2 - 2\gamma \sum_{i=1}^n (x_i - a_n) + \sum_{i=1}^n \gamma^2 + (x_{n+1} - a_{n+1})^2$
	$\displaystyle = s_n + 0 + n \gamma^2 + (x_{n+1} - a_{n+1})^2\,.$

Now observe:

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

hence we obtain:

$\displaystyle s_{n+1} = s_n + n\gamma^2 + n^2 \gamma^2 = s_n + n(n+1) \gamma^2$	$\displaystyle = s_n + n \gamma \delta$
	$\displaystyle = s_n + ( x_{n+1} - a_{n+1}) \delta\,.$

Note that the number to be added to 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 .)

The recurrence relation for the sample covariance of two lists of numbers $x_1, x_2, \dotsc$ and $y_1, y_2, \dotsc$ can be derived similarly. If and denote the arithmetic means of first numbers of each of the two lists respectively, then the sum of adjusted products

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

can be incrementally updated by

$\displaystyle 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)\,.$

Bibliography

1: B. P. Welford. ``Note on a Method for Calculating Corrected Sums of Squares and Products''. Technometrics, Vol. 4, No. 3 (Aug., 1962), p. 419-420.
2: ``Algorithms for calculating variance''. Wikipedia, The Free Encyclopedia. Accessed 25 February 2007.

"one-pass algorithm to compute sample variance" is owned by stevecheng.

(view preamble)

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: products, covariance, recurrence relation, negative, residuals, arithmetic mean, algebraic, simple, algorithm, variance, sample mean, running, squares, sum, digits, subtraction, absolute value, mean, numbers, sample variance, iteration, calculate

This is version 6 of one-pass algorithm to compute sample variance, born on 2007-02-24, modified 2007-04-11.
Object id is 8981, canonical name is OnePassAlgorithmToComputeSampleVariance.
Accessed 2500 times total.

Classification:

AMS MSC:	62-00 (Statistics :: General reference works )
	65-00 (Numerical analysis :: General reference works )
	68W01 (Computer science :: Algorithms :: General)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact

post | correct | update request | add example | add (any)