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:
mean = Mean(list) for i = 0 to list.size stdev = stdev + (list[i] - mean)^2 stdev = sqrRoot( stdev / list.size )
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=n−1∑nj=1Xj and s2n defined similarly as the n‘th sample variance (I use a denominator of n−1 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
Expand this to get s2n=(n−2)s2n−1+(n−1)(ˉXn−1−ˉXn)2+2∑n−1j=1(Xj−ˉXn−1)(ˉXn−1−ˉXn)+(Xn−ˉXn)2n−1
and it is easy to show that the summation term above is equal to 0 which gives s2n=(n−2)s2n−1+(n−1)(ˉXn−1−ˉXn)2+(Xn−ˉXn)2n−1.
EDIT: I assumed you already have an incremental expression for the sample mean. It is much easier to get that: ˉXn=n−1[Xn+(n−1)ˉXn−1].