From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=ham autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,608f4b25931220fc
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2004-01-26 19:39:45 PST
Path: 
 archiver1.google.com!news2.google.com!news.maxwell.syr.edu!elnk-pas-nf1!elnk-nf2-pas!newsfeed.earthlink.net!attbi_feed3!attbi_feed4!attbi.com!attbi_s52.POSTED!not-for-mail
From: "Steve" <nospam_steved94@comcast.net>
Newsgroups: comp.lang.ada
References: <86k73e9uzk.fsf@lucretia.kaos>
Subject: Re: Incremental statistics functions
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2800.1158
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
Message-ID: <44lRb.124968$sv6.677741@attbi_s52>
NNTP-Posting-Host: 67.160.161.145
X-Complaints-To: abuse@comcast.net
X-Trace: attbi_s52 1075174784 67.160.161.145 (Tue, 27 Jan 2004 03:39:44 GMT)
NNTP-Posting-Date: Tue, 27 Jan 2004 03:39:44 GMT
Organization: Comcast Online
Date: Tue, 27 Jan 2004 03:39:44 GMT
Xref: archiver1.google.com comp.lang.ada:4874
Date: 2004-01-27T03:39:44+00:00
List-Id: <comp.lang.ada>

An incremental algorithm for standard deviation is easy.  An incremental
algorithm for variance (as far as I know) is not possibile.  It is my
understanding that standard deviation is really an approximation of variance
that is easier to calculate.

As I recall (it's been a while):
  Variance is the average deviation from the average value of a set of
values.

To find variance you must first find the average of all values.  Then you
must take the absolute value of the average of the difference between the
average and each individual value.

  avg = sum of values / number of values
  variance = (sum over i ( abs( value(i) - avg ) )) / number of values

That "abs" in the formula makes things tough for incremental algorithms.

The standard deviation approximates variance as

  std dev = sqrt( sum of i(( value(i) - avg)^2) )

Which transforms to:

  std dev = sqrt( (avg of value^2) - (avg of value)^2 )

To calculate an incremental standard deviation you keep track of:
   the sum of all values
   the sum of the squares of values
   the number of values
Then do a straight calculation after each new value is added.

I hope this helps,
Steve
(The Duck)


"Mats Karlssohn" <sm5tfx@telia.com> wrote in message
news:86k73e9uzk.fsf@lucretia.kaos...
> Hi
>
> I'm trying to find algorithms to calculate standard-deviation and variance
> _without_ keeping a buffer of the samples. I'm not really shure if I'm
right
> to call them incremental algorithms but I couldn't find a better
expression.
> Basically I don't want to keep a (limited) buffer of samples but would
like
> to add the values one at a time when they are calculated.
>
> Probably I googled bad, since I didn't find anything I could understand.
>
> Any suggestions please?
>
> -- 
> Mats Karlssohn (SM5TFX), sm5tfx@telia.com
> "Without mistakes there is no forgiving, without forgiving there is no
love"