3
$\begingroup$

I'm trying to develop a real time algorithm for finding level areas of an electrical signal.

To do so I need to find the variance for a particular rolling time interval.

From John Cook's blog and the Art of Computer Programming the algorithm for quickly determining variance is:

Mk = Mk-1 + (xk - Mk-1)/k

Sk = Sk-1 + (xk - Mk-1) * (xk - Mk)

Where the kth estimate of the variance is:

$ s^2 = S_k / (k-1) $

This works great, but I need to keep a 'rolling' variance of 100 samples. With each step I would add one new sample and take the 100th sample off the list.

If I know the value of xk-100 is there a quick algorithm for 'erasing' it from the variance result?

1 Answers 1

2

Just work the math on that formula in reverse. Let $S_{m,n}$ be the value of Knuth's $S$ (variance times samples-minus-1) for elements $m..n$ of your rolling stream; then just as $S_{m,n+1} = S_{m,n}+(x_n-M_{m,n-1})\cdot(x_n-M_{m,n})$, you have $S_{m, n} = S_{m+1,n} + (x_m-M_{m+1,n})\cdot(x_m-M_{m,n})$ — or in other words, $S_{m+1,n} = S_{m,n} - (x_m-M_{m+1,n})\cdot(x_m-M_{m,n})$. At each step, where you have your rolling value $S = S_{k-99,k}$, first compute $S_{k-98,k}$ with one application of the formula for $S_{m+1,n}$ in terms of $S_{m,n}$ and then one application of the formula for $S_{m,n+1}$ in terms of $S_{m,n}$. Note that you'll need your 'before and after' rolling mean values to do this, but finding $M_{m,n}$ and the associated values is (obviously) much easier.