Fast way to recalculate average and standard deviation as new values arrive

Question

Say I have a stream of values arriving all the time, and I want to get the average and standard deviation of only the last $n$ values.

If I already have the average $V$ for values $v_1, ..., v_n$, then when $v_{n+1}$ arrives, all I have to do to find the new average $V'$ for values $v_2, ..., v_{n+1}$ is:

$$ V' = V - \frac{v_1}{n} + \frac{v_{n+1}}{n} $$

However, how can I do this for the standard deviation? Is there any such shortcut?

EDIT:

The purpose of this question is to minimize the computation necessary for a software I'm developing. Part of it relies on estimating the communication latency of other processes (but only for the most recent messages received).

You can find a good discussion here: https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance — kjetil b halvorsen, Mar 31 '14 at 10:42

Claude Leibovici · Answer 1 · 2014-03-31T09:54:47.710

2

Hint

By definition $$\sigma=\sqrt{\frac{\sum _{i=1}^n (v_i-\mu )^2}{n}}$$ that is to say that $$n \sigma^2=\sum _{i=1}^n (v_i-\mu )^2=\sum _{i=1}^n v_i^2-2 \mu \sum _{i=1}^n v_i+n \mu^2$$ Now, do the same as you did for the average.

I am sure that you can take from here.

edited Mar 31 '14 at 09:54

answered Mar 31 '14 at 09:25

Claude Leibovici

260,315

1

Shouldn't the last bit of your equation be $\sum_{i=1}^n \mu^2$? Instead of just $\mu^2$? – Eduardo Bezerra Mar 31 '14 at 09:53
Yes sir ! Good point. I edit my answer. Thanks. – Claude Leibovici Mar 31 '14 at 09:54
So, let's call $n\sigma^2$ as $\delta$ (not sure if this is a good letter). The old average is $\mu$ and the new average is $\mu'$. So, $\delta' = \delta - v_1^2 + v_{n+1}^2 + 3\mu^2n - 3\mu'^2n$? – Eduardo Bezerra Mar 31 '14 at 11:33
I meant $\delta' = \delta - v_1^2 + v_{n+1}^2 + \mu^2n - \mu'^2n$. – Eduardo Bezerra Mar 31 '14 at 11:39

Fast way to recalculate average and standard deviation as new values arrive

1 Answers1

Linked