- Algorithms for calculating variance
play a major role in statistical computing. A key problem in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead toAlgorithm s for calculatingvariance numerical instability as well as toarithmetic overflow when dealing with large values.**I. Naïve algorithm**The

formula for calculating the variance of an entire population of size "n" is::$sigma^2\; =\; displaystylefrac\; \{sum\_\{i=1\}^\{n\}\; x\_i^2\; -\; (sum\_\{i=1\}^\{n\}\; x\_i)^2/n\}\{n\}.\; !$

The formula for calculating an unbiased estimate of the population variance from a finite sample of "n" observations is:

:$s^2\; =\; displaystylefrac\; \{sum\_\{i=1\}^\{n\}\; x\_i^2\; -\; (sum\_\{i=1\}^\{n\}\; x\_i)^2/n\}\{n-1\}.\; !$

Therefore a naive algorithm to calculate the estimated variance is given by the following

pseudocode :n = 0 sum = 0 sum_sqr = 0 foreach x in data: n = n + 1 sum = sum + x sum_sqr = sum_sqr + x*x end for mean = sum/n variance = (sum_sqr - sum*mean)/(n - 1)

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

`sum_sqr`

and`sum * mean`

can be very similar numbers, the precision of the result can be much less than the inherent precision of thefloating-point arithmetic used to perform the computation. This is particularly bad if the variance is small relative to the sum of the numbers.**II. Two-pass algorithm**An alternate approach, using a different formula for the variance, is given by the following pseudocode:

n = 0 sum1 = 0 foreach x in data: n = n + 1 sum1 = sum1 + x end for mean = sum1/n sum2 = 0 foreach x in data: sum2 = sum2 + (x - mean)^2 end for variance = sum2/(n - 1)

This algorithm is often more numerically reliable than the naïve algorithm I for large sets of data, although it can be worse if much of the data is very close to but not precisely equal to the mean and some are quite far away from it.

The results of both of these simple algorithms (I and II) 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.**IIa. Compensated variant**The compensated-summation version of the algorithm above reads:

n = 0 sum1 = 0 foreach x in data: n = n + 1 sum1 = sum1 + x end for mean = sum1/n sum2 = 0 sumc = 0 foreach x in data: sum2 = sum2 + (x - mean)^2 sumc = sumc + (x - mean) end for variance = (sum2 - sumc^2/n)/(n - 1)

**III. On-line algorithm**It is often useful to be able to compute the variance in a single pass, inspecting each value $x\_i$ only once; for example, when the data are being collected without enough storage to keep all the values, or when costs of memory access dominate those of computation. For such an

online algorithm , arecurrence relation is required between quantities from which the required statistics can be calculated in a numerically stable fashion.The following formulas can be used to update the

mean and (estimated) variance of the sequence, for an additional element $x\_\{mathrm\{new$. Here, "m" denotes the estimate of the population mean(using the sample mean), "s"^{2}_{n-1}the estimate of the population variance, "s"^{2}_{n}the estimate of the sample variance, and "n" the number of elements in the sequence before the addition.:$m\_\{mathrm\{new\; =\; frac\{n\; ;\; m\_\{mathrm\{old\; +\; x\_\{mathrm\{new\}\{n+1\}\; =\; m\_\{mathrm\{old\; +\; frac\{x\_\{mathrm\{new\; -\; m\_\{mathrm\{old\}\{n+1\}\; !$

:$s^2\_\{mathrm\{n-1,\; new\; =\; frac\{(n-1)\; ;\; s^2\_\{mathrm\{n-1,\; old\; +\; (x\_\{mathrm\{new\; -\; m\_\{mathrm\{new)\; ,\; (x\_\{mathrm\{new\; -\; m\_\{mathrm\{old)\}\{n\}\; ;\; ;\; ,\; ,\; ;\; ,\; mathrm\{n>0\}\; !$

:$s^2\_\{mathrm\{n,\; new\; =\; frac\{n\; ;\; s^2\_\{mathrm\{n,\; old\; +\; (x\_\{mathrm\{new\; -\; m\_\{mathrm\{new)\; ,\; (x\_\{mathrm\{new\; -\; m\_\{mathrm\{old)\}\{n+1\}.$

It turns out that a more suitable quantity for updating is the sum of squares of differences from the (current) mean, $sum\_\{i=1\}^n\; (x\_i\; -\; m)^2$, here denoted $M\_2$:

:$M\_mathrm\{2,new\}!\; =\; M\_mathrm\{2,old\}\; +\; (x\_mathrm\{new\}\; -\; m\_mathrm\{old\})(x\_mathrm\{new\}\; -\; m\_mathrm\{new\})$:$s^2\_mathrm\{n\}\; =\; frac\{M\_2\}\{n\}$:$s^2\_mathrm\{n-1\}\; =\; frac\{M\_2\}\{n-1\}$

A numerically stable algorithm is given below. It also computes the mean.This algorithm is due to Knuth, [

] who cites Welford. [Donald E. Knuth (1998). "The Art of Computer Programming ", volume 2: "Seminumerical Algorithms", 3rd edn., p. 232. Boston: Addison-Wesley.*B. P. Welford (1962). [*]*http://www.jstor.org/view/00401706/ap040015/04a00090/0 "Note on a method for calculating corrected sums of squares and products"*] . "Technometrics " 4(3):419–420.n = 0 mean = 0 M2 = 0 foreach x in data: n = n + 1 delta = x - mean mean = mean + delta/n M2 = M2 + delta*(x - mean) // This expression uses the new value of mean end for variance_n = M2/n variance = M2/(n - 1)

This algorithm is much less prone to loss of precision due to massive 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, first compute and subtract an estimate of the mean, and then use this algorithm on the residuals.

A slightly more convenient form allows one to calculate the standard deviation without having to explicitly calculate the new mean. If $n$ is the number of elements in the sequence after the addition of the new element, then one has

$s^2\_\{mathrm\{n-1,\; new\; =\; frac\{(n-2)s^2\_\{mathrm\{n-1,\; old+frac\{n-1\}\{n\}left(x\_\; ext\{new\}-m\_\; ext\{old\}\; ight)^2\}\{n-1\}$

**IV. Weighted incremental algorithm**When the observations are weighted, West (1979) [

*D. H. D. West (1979). "*] suggests this incremental algorithm:Communications of the ACM ", 22, 9, 532-535: "Updating Mean and Variance Estimates: An Improved Method"n = 0 foreach x in the data: if n=0 then n = 1 mean = x S = 0 sumweight = weight else n = n + 1 temp = weight + sumweight S = S + sumweight*weight*(x-mean)^2 / temp mean = mean + (x-mean)*weight / temp sumweight = temp end if end for Variance = S * n / ((n-1) * sumweight) // if sample is the population, omit n/(n-1)

**V. Parallel algorithm**Chan et al. [

*Citation*] note that the above on-line algorithm III is a special case of an algorithm that works for any partition of the sample $X$ into sets $X^A$, $X^B$::$delta!\; =\; m^B\; -\; m^A$:$m^X\; =\; m^A\; +\; deltacdotfrac\{N^B\}\{N^X\}$:$M\_2^X\; =\; M\_2^A\; +\; M\_2^B\; +\; delta^2cdotfrac\{N^A\; N^B\}\{N^X\}$.This may be useful when, for example, multiple processing units may be assigned to discrete parts of the input.

last1 = Chan | first1 = Tony F.

last2 = Golub | first2 = Gene H. | author2-link = Gene H. Golub

last3 = LeVeque | first3 = Randall J.

contribution = Updating Formulae and a Pairwise Algorithm for Computing Sample Variances.

title = Technical Report STAN-CS-79-773

publisher = Department of Computer Science, Stanford University

year = 1979

contribution-url = ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/79/773/CS-TR-79-773.pdf .**Higher-order statistics**Terriberry [

*Citation*] extends Chan's formulae to calculating the third and fourth

last=Terriberry

first=Timothy B.

year=2007

title=Computing Higher-Order Moments Online

url=http://people.xiph.org/~tterribe/notes/homs.htmlcentral moment s, needed for example when estimatingskewness andkurtosis ::$M\_3^X\; =\; M\_3^A\; +\; M\_3^B\; +\; delta^3frac\{N^A\; N^B\; (N^A\; -\; N^B)\}\{(N^X)^2\}\; +\; 3deltafrac\{N^AM\_2^B\; -\; N^BM\_2^A\}\{N^X\}$:$egin\{align\}M\_4^X\; =\; M\_4^A\; +\; M\_4^B\; +\; delta^4frac\{N^A\; N^B\; left((N^A)^2\; -\; N^A\; N^B\; +\; (N^B)^2\; ight)\}\{(N^X)^3\}\; \backslash \; +\; 6delta^2frac\{(N^A)^2\; M\_2^B\; +\; (N^B)^2\; M\_2^A\}\{(N^X)^2\}\; +\; 4deltafrac\{N^AM\_3^B\; -\; N^BM\_3^A\}\{N^X\}\; \backslash end\{align\}$Here the $M\_k$ are again the sums of powers of differences from the mean $Sigma(x\; -\; overline\{x\})^k$, giving:skewness: $g\_1\; =\; frac\{sqrt\{n\}\; M\_3\}\{M\_2^\{3/2,$:kurtosis: $g\_2\; =\; frac\{n\; M\_4\}\{M\_2^2\}.$

For the incremental case (i.e., $B\; =\; \{x\}$), this simplifies to::$delta!\; =\; x\; -\; m$:$m\text{'}\; =\; m\; +\; frac\{delta\}\{n\}$:$M\_2\text{'}\; =\; M\_2\; +\; delta^2\; frac\{\; n-1\}\{n\}$:$M\_3\text{'}\; =\; M\_3\; +\; delta^3\; frac\{\; (n\; -\; 1)\; (n\; -\; 2)\}\{n^2\}\; -\; frac\{3delta\; M\_2\}\{n\}$:$M\_4\text{'}\; =\; M\_4\; +\; frac\{delta^4\; (n\; -\; 1)\; (n^2\; -\; 3n\; +\; 3)\}\{n^3\}\; +\; frac\{6delta^2\; M\_2\}\{n^2\}\; -\; frac\{4delta\; M\_3\}\{n\}$

It should be noted that by preserving the value $delta\; /\; n$, only one division operation is needed and thus that the higher-order statistics can be calculated for little incremental cost.

**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 Algorithm I and Algorithm II compute these values correctly. Next consider the sample (10

^{8}+ 4, 10^{8}+ 7, 10^{8}+ 13, 10^{8}+ 16), which gives rise to the same estimated variance as the first sample. Algorithm II computes this variance estimate correctly, but Algorithm I returns 29.333333333333332 instead of 30. While this loss of precision may be tolerable and viewed as a minor flaw of Algorithm I, it is easy to find data that reveal a major flaw in the naive algorithm: Take the sample to be (10^{9}+ 4, 10^{9}+ 7, 10^{9}+ 13, 10^{9}+ 16). Again the estimated population variance of 30 is computed correctly by Algorithm II, but the naive algorithm now computes it as −170.66666666666666. This is a serious problem with Algorithm I, since the variance can, by definition, never be negative.**See also***

Computational formula for the variance **References****External links***

*Wikimedia Foundation.
2010.*