Re: standard deviation, but without the mean


"Ray Koopman" <koopman@xxxxxx> wrote in message
news:1141669275.577944.112830@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
richardstartz@xxxxxxxxxxx wrote:
The standard deviation is the square root of the variance (of course).
There's a standard formula for computing the variance from a running
sum. Suppose Xsum is the sum of the the first n numbes and that X2 is
the sum of the squares. Then

var = X2/n - (Xsum/n)^2

Just keep track if X2 and Xsum as you go.

Using running totals can sometimes lead to cancellation errors.
See http://tinyurl.com/d6ax2 for a stable algorithm.

+++++++++++++++++++++++++++++++++++
Actually this is not a correct algorithm, just an approximation.

I've just gone through Welford's algorithm (a one pass calculation) using
xnumbers on the NIST data sets and have found Welford to obtain correct
values. The errors come in due to the general problem of summation of lists
of numbers, which no algorithm can fix. The solution of course is to do it
with as many digits as possible, so that the summation errors are not
important.

For example, running Welford's on the NIST NumAcc4 data set (1001 values)
using a 30 digit exact computation comes out to the theoretical value, with
the error in the least 9 digits (21 accurate digits).. By using Kahan's
method of summation, this reduces the error to about 7 digits.

If people would make the effort to read Knuth, a lot of the misconceptions
would disappear. Welford published in Technometrics, 1962, pg 419-420. All
this is in Knuth. Apparently everybody else missed it.

David Heiser


.

Relevant Pages

  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: Simplified form for sum of permutations ? Combinitorics question
    ... If Sis the sum of products of all combinations of x_1,...,x_n ... If Nis the number of operations for computing Sthis way, ... This formula and algorithm is basically the one above which gives 11 ... enormous difference. ...
    (sci.math)
  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)