Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.