World's most popular travel blog for travel bloggers.

Find variance within one pass

, , No Comments
Problem Detail: 

Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity?

My intuition is that it is not possible. But how do I prove it mathematically?

Asked By : Will

Answered By : D.W.

Yes, it's possible. If you know the count of the number of values, the sum of the values, and the sum of the squares of the values, you can derive the variance. In particular,

$$\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2.$$

You can calculate the first term from the sum of the squares of the values, and you can calculate the second term from the sum of the values.

However, beware the caveats mentioned here: https://en.wikipedia.org/wiki/Variance#Formulae_for_the_variance

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44849

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback