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 have bunch of values, for example {1,2,3,4}. I need to measure variance in a very efficient way. On wikipedia variance is defined as sum of squared differences between the data examples and the mean, and then you normalize that sum with 1/n, where n is the number of data examples. One improvement is to skip the normalization. Any other ways I can improve this and make it less expensive to compute?

Thanks

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I presume you're talking implementing the calculation in software (if it is to be done by hand, some of the remarks might be irrelevant).

The averaging/normalization at the end is usually the least expensive step of the calculations; after all, it's just one arithmetical operation. Depending on what your measure of efficiency is, you might find the following formula useful: $$\mathrm{Var}=\mathrm{E}(X^2)-(\mathrm{E}(X))^2$$

If you are dealing with $n$ samples $x_1, x_2, \ldots, x_n$, it can be expressed as follows: $$\mathrm{Var}=\frac{1}{n}\sum_{i=1}^n x_i^2 - \left(\frac{1}{n}\sum_{i=1}^n x_i\right)^2$$

Thus, in order to calculate the variance of the given samples, you only need to find their sum and sum of their squares, both divided by $n$ and perform one squaring and one subtraction at the end. The total number of arithmetic operations will then be $(n+1)$ squarings, $(2n-2)$ additions and one subtraction... which looks quite efficient to me. As an extra bonus, you will also get the (arithmetic) mean of the samples. Finally, this approach also allows you to process the samples as they are appearing without storing them (of course, unless you need them for other purposes); allowing you to process lots of samples without increasing the memory requirements. The only possible problem could arise if the variance is very small and thus the two quantities you're going to subtract are very close; you'd need to be well aware of the capabilities and limitations of your real-number processing tools.

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.