5
$\begingroup$

Say I have a (infinite) sequences like 1, 3, 2, 2, 1, 3 ...

I want to estimate their mean and variance of the sequence at time $t$.

But I won't have enough storage to keep all the data seen previously.

I know I can compute the mean by only keeping the sum of the sequence by far, then divide through by time $t$.

But how can I compute/estimate the variance (using a constant amount of storage)? Is there any trick/model for this?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
7
$\begingroup$

The proper answer to your question is named online sample variance, and in general online statistics. It's named online because you update the current value of the sample statistic and don't look back at that number.

In order to find an online algorithm to handle that what you need is to break the definition of sample variance into two kind of terms: first kind would use previous information and the second kind the new value.

For simplicity I let's look at sample mean: $m_n = \frac{1}{n} \sum_{i=1}^{n} x_i$, where $n$ is the number of elements and $x_i$ is the element from the stream at $i$-th position.

Let's do some tricks:

$$m_n = \frac{1}{n}\sum_{i=1}^{n} x_i = \frac{n-1}{n(n-1)}(\sum_{i=1}^{n-1} x_i + x_n) = \frac{n-1}{n}(\frac{1}{n-1}\sum_{i=1}^{n-1}x_i) + \frac{1}{n}x_n$$

Now you recognize in the last expression in parenthesis the term $m_{n-1}$, so we have the following recursive relation:

$$m_n = \frac{n-1}{n}m_{n-1} + \frac{1}{n}x_n$$

which states that we have to know the number of elements and the mean from a current step to compute the next mean by using also the next element.

Similar recursive equations can be developed for minimum, maximum, standard deviation, variance, skewness and kurtosis.

For a full explanation look at the beautiful article by John D. Cook. I implemented myself such an online statistic tool in Java, which you can find here

Improve this answer
$\endgroup$
2
$\begingroup$

It seems after some looking around, that the algorithms given in this technical report by Chan, Golub, and LeVeque from 1983 are still the state of the art.

Improve this answer
$\endgroup$
1
$\begingroup$

My intuition, might not be correct:

Lets say you divide sequence in 2 groups having same number of elements, calculate there mean (mean1 and mean2) and variances (variance1, variance 2) , For calculating variance 2 you can use combined mean of both the sequences i.e. (mean1 + mean2)/2, Now based on this mean (mean3) you can correct variance of first sequence lets call it variance3, Now combined variance will be (variance3 + variance2)/2

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you and sorry I just realized I used a really terrible example, indeed I only want the variance of a single sequence, and I can't compute it directly because I don't have enough space to keep all the data (because there's infinite amount of them), so I think what I'm asking is is there some trick/model to compute/estimate the variance with a constant amount of storage? $\endgroup$
    – dontloo
    Commented Mar 4, 2016 at 4:59
  • $\begingroup$ Yes, I considered only single sequence divided in 2 sub sequences having equal elements, but the procedure can be used recursively if series is divided more than two sub sequences. $\endgroup$
    – Siddhesh
    Commented Mar 4, 2016 at 5:12

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