Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values.
Contents
Naïve algorithm
A formula for calculating the variance of an entire population of size N is:
Using Bessel's correction to calculate an unbiased estimate of the population variance from a finite sample of n observations, the formula is:
Therefore, a naive algorithm to calculate the estimated variance is given by the following:
This algorithm can easily be adapted to compute the variance of a finite population: simply divide by N instead of n − 1 on the last line.
Because SumSq and (Sum×Sum)/n can be very similar numbers, cancellation can lead to the precision of the result to be much less than the inherent precision of the floating-point arithmetic used to perform the computation. Thus this algorithm should not be used in practice. This is particularly bad if the standard deviation is small relative to the mean. However, the algorithm can be improved by adopting the method of the assumed mean.
Computing shifted data
We can use a property of the variance to avoid the catastrophic cancellation in this formula, namely the variance is invariant with respect to changes in a location parameter
with
the closer
If we take just the first sample as
this formula facilitates as well the incremental computation, that can be expressed as
Two-pass algorithm
An alternative approach, using a different formula for the variance, first computes the sample mean,
and then computes the sum of the squares of the differences from the mean,
where s is the standard deviation. This is given by the following pseudocode:
This algorithm is numerically stable if n is small. However, the results of both of these simple algorithms ("Naïve" and "Two-pass") can depend inordinately on the ordering of the data and can give poor results for very large data sets due to repeated roundoff error in the accumulation of the sums. Techniques such as compensated summation can be used to combat this error to a degree.
Online algorithm
It is often useful to be able to compute the variance in a single pass, inspecting each value
The following formulas can be used to update the mean and (estimated) variance of the sequence, for an additional element xn. Here, xn denotes the sample mean of the first n samples (x1, ..., xn), s2n their sample variance, and σ2n their population variance.
These formulas suffer from numerical instability. A better quantity for updating is the sum of squares of differences from the current mean,
A numerically stable algorithm for the sample variance is given below. It also computes the mean. This algorithm was found by Welford, and it has been thoroughly analyzed. It is also common to denote
This algorithm is much less prone to loss of precision due to catastrophic cancellation, but might not be as efficient because of the division operation inside the loop. For a particularly robust two-pass algorithm for computing the variance, one can first compute and subtract an estimate of the mean, and then use this algorithm on the residuals.
The parallel algorithm below illustrates how to merge multiple sets of statistics calculated online.
Weighted incremental algorithm
The algorithm can be extended to handle unequal sample weights, replacing the simple counter n with the sum of weights seen so far. West (1979) suggests this incremental algorithm:
Parallel algorithm
Chan et al. note that the above "On-line" algorithm is a special case of an algorithm that works for any partition of the sample
This may be useful when, for example, multiple processing units may be assigned to discrete parts of the input.
Chan's method for estimating the mean is numerically unstable when
Example
Assume that all floating point operations use the standard IEEE 754 double-precision arithmetic. Consider the sample (4, 7, 13, 16) from an infinite population. Based on this sample, the estimated population mean is 10, and the unbiased estimate of population variance is 30. Both "Naïve" algorithm and "Two-pass" algorithm compute these values correctly. Next consider the sample (108 + 4, 108 + 7, 108 + 13, 108 + 16), which gives rise to the same estimated variance as the first sample. "Two-pass" algorithm computes this variance estimate correctly, but "Naïve" algorithm returns 29.333333333333332 instead of 30. While this loss of precision may be tolerable and viewed as a minor flaw of "Naïve" algorithm, it is easy to find data that reveal a major flaw in the naive algorithm: Take the sample to be (109 + 4, 109 + 7, 109 + 13, 109 + 16). Again the estimated population variance of 30 is computed correctly by "Two-pass"" algorithm, but "Naïve" algorithm now computes it as −170.66666666666666. This is a serious problem with "Naïve" algorithm and is due to catastrophic cancellation in the subtraction of two similar numbers at the final stage of the algorithm.
Higher-order statistics
Terriberry extends Chan's formulae to calculating the third and fourth central moments, needed for example when estimating skewness and kurtosis:
Here the
For the incremental case (i.e.,
By preserving the value
An example of the online algorithm for kurtosis implemented as described is:
Pébaÿ further extends these results to arbitrary-order central moments, for the incremental and the pairwise cases, and subsequently Pébaÿ et al. for weighted and compound moments. One can also find there similar formulas for covariance.
Choi and Sweetman offer two alternative methods to compute the skewness and kurtosis, each of which can save substantial computer memory requirements and CPU time in certain applications. The first approach is to compute the statistical moments by separating the data into bins and then computing the moments from the geometry of the resulting histogram, which effectively becomes a one-pass algorithm for higher moments. One benefit is that the statistical moment calculations can be carried out to arbitrary accuracy such that the computations can be tuned to the precision of, e.g., the data storage format or the original measurement hardware. A relative histogram of a random variable can be constructed in the conventional way: the range of potential values is divided into bins and the number of occurrences within each bin are counted and plotted such that the area of each rectangle equals the portion of the sample values within that bin:
where
where the superscript
The second approach from Choi and Sweetman is an analytical methodology to combine statistical moments from individual segments of a time-history such that the resulting overall moments are those of the complete time-history. This methodology could be used for parallel computation of statistical moments with subsequent combination of those moments, or for combination of statistical moments computed at sequential times.
If
where
The benefit of expressing the statistical moments in terms of
where the subscript
Known relationships between the raw moments (
Covariance
Very similar algorithms can be used to compute the covariance. The naive algorithm is:
For the algorithm above, one could use the following Python code:
As for the variance, the covariance of two random variables is also shift-invariant, so given that
and again choosing a value inside the range of values will stabilize the formula against catastrophic cancellation as well as make it more robust against big sums. Taking the first value of each data set, the algorithm can be written as:
The two-pass algorithm first computes the sample means, and then the covariance:
The two-pass algorithm may be written as:
A slightly more accurate compensated version performs the full naive algorithm on the residuals. The final sums
A slight modification of the online algorithm for computing the variance yields an online algorithm for the covariance:
A stable one-pass algorithm exists, similar to the one above, that computes co-moment
The apparent asymmetry in that last equation is due to the fact that
Thus we can compute the covariance as
Likewise, there is a formula for combining the covariances of two sets that can be used to parallelize the computation: