incremental computation of standard deviation

How can I compute the standard deviation in an incremental way (using the new value and the last computed mean and/or std deviation) ?

for the non incremental way, I just do something like:
SN=1NNi=1(xi¯x)2.

mean = Mean(list)
for i = 0 to list.size
   stdev = stdev + (list[i] - mean)^2
stdev = sqrRoot( stdev / list.size )

Answer

I think the easiest way to do this is with an orthogonality trick. I’ll show how to incrementally compute the variance instead of the standard deviation. Let X1,X2,... be an iid sequence of random variables with ˉX=n1nj=1Xj and s2n defined similarly as the n‘th sample variance (I use a denominator of n1 instead of n in your picture to keep things unbiased for the variance, but you can use the same argument just adding 1 to all the terms with n in them). First write
s2n=nj=1(XjˉXn)2n1=nj=1(XjˉXn1+ˉXn1ˉXn)2n1.
Expand this to get s2n=(n2)s2n1+(n1)(ˉXn1ˉXn)2+2n1j=1(XjˉXn1)(ˉXn1ˉXn)+(XnˉXn)2n1
and it is easy to show that the summation term above is equal to 0 which gives s2n=(n2)s2n1+(n1)(ˉXn1ˉXn)2+(XnˉXn)2n1.

EDIT: I assumed you already have an incremental expression for the sample mean. It is much easier to get that: ˉXn=n1[Xn+(n1)ˉXn1].

Attribution
Source : Link , Question Author : shn , Answer Author : guy

Leave a Comment