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 without having to have every number available in computer memory before beginning processing.
Let denote the data. The naïve formula for calculating the sample variance in one pass,
suffers from computational round-off error. If the mean is large in absolute value, and is close to , then the subtraction at the end will tend to lose significant digits on the result. Also, in rare cases, the sum of squares 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.
We want to express and in terms of the old values and .
For convenience, let and . Then we have
For the variance calculation, we have
hence we obtain:
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 happens to be very small compared to .)
The recurrence relation for the sample covariance of two lists of numbers and 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
can be incrementally updated by
- 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 “http://en.wikipedia.org/wiki/Algorithms_for_calculating_varianceAlgorithms for calculating variance”. Wikipedia, The Free Encyclopedia. Accessed 25 February 2007.
|Title||one-pass algorithm to compute sample variance|
|Date of creation||2013-03-22 16:45:19|
|Last modified on||2013-03-22 16:45:19|
|Last modified by||stevecheng (10074)|