2

I would like to subscribe to a WebSocket stream which will supply me with many numbers per second. From this data, I would like to calculate the variance of say the last 1000 numbers.

How can I do this in a rolling fashion? That is, I would like some computation comparable to this one for the mean of the last 1000 numbers:

$$\rm{mean}_{i+1} = \rm{mean}_{i} + \frac{1}{1000}\left(x_{i+1}-x_{i-999}\right)$$

Thanks in advance for any help. Ben

Ben Crossley
  • 2,544
  • Do you know the formula for calculating the variance of a set of numbers from their sum and the sum of their squares? – JonathanZ Feb 04 '21 at 22:49
  • 1
    BTW, from your formula for the mean, I assume you're planning on keeping the last 1000 numbers around, so that you can subtract off $x_{i-999}$? So you can use that same value to update the sum of squares too. – JonathanZ Feb 04 '21 at 22:52

2 Answers2

1

$$\rm{variance}_{i+1} = \frac{1}{1000}\sum_{j=i-999}^{i+1}\left(x_j-\rm{mean}_{i+1}\right)^2\\ =\frac{1}{1000}(x_{i+1}^2-x_{i-999}^2)+\rm{variance}_{i}-\rm{mean}_{i+1}^2+\rm{mean}_{i}^2,$$ where you already computed $\rm{mean}_{i+1}$ according to your equation. If you wonder why the equality holds, see here.

Nameless
  • 4,045
  • 2
  • 20
  • 36
1

This is basically the same idea as Nameless' answer, but I think it's cleaner if you just keep and update $SX$, the sum of the terms, and $SX^2$, the sum of their squares, update those via

$$\begin{align} SX_{i+1} &= SX_i + x_{i+1}-x_{i-999}\\ SX^2_{i+1} &= SX^2_i + x_{i+1}^2-x_{i-999}^2\\ \end{align} $$

and then compute

$$\begin{align} mean_{i+1} &= SX_{i+1}/1000\\ var_{i+1} &= \frac{1}{1000}SX^2_{i+1} - (\frac{1}{1000}SX_{i+1})^2\\ &= \frac{1}{1000}SX^2_{i+1} - mean_{i+1}^2\\ \end{align} $$

(This is the way that old calculators would let you accumulate an arbitrary number of data values and then let you compute mean and variance at the end.)

There is a possible issue in that you have to be able to store a number of magnitude roughly $1000*(\text{typical }x)^2$. Hopefully your values aren't too large.

If you're really worried about numerical instability, @awkward's link to Wellford's online algorithm looks to be the state-of-the-art; I'd check that out if your output values start to go wrong after you've been running for a while.

JonathanZ
  • 10,615
  • Thank you for your help and your caution too. Storing those values should be fine. The numbers are of the order $10^{-5}$. – Ben Crossley Feb 05 '21 at 09:32
  • Before I have accrued 1000 data points I can just omit the $-x_{i-999}$ part in both formulas can't I? That should initialise the algorithm correctly? – Ben Crossley Feb 05 '21 at 14:29
  • 1
    Many of the methods you may find in statistics textbooks suffer from numerical instability. Instead, consider Welford's Online Algorithm – awkward Feb 05 '21 at 15:28
  • 1
    @BenCrossley: You could do that, but considering that you're going to have to keep a buffer containing the last 1000 values seen, you could achieve the same effect instead by just initializing that with all zeros and not having to check if i <1000 each time. Either way you might get some "iffy' numbers on the first few iterations; you'll have to decide if that will throw things off or if you can just ride through that initial bump. – JonathanZ Feb 06 '21 at 19:05
  • @awkward - That's such a good resource that I added it to my answer. Hope you don't mind. – JonathanZ Feb 06 '21 at 19:09
  • The formula for variance is missing a $\frac{}{1000}$ – Ben Crossley Feb 11 '21 at 21:43
  • D'oh! That's what happens when I'm just copying a formula. Thanks for pointing it out. – JonathanZ Feb 11 '21 at 23:55