If you google “how do i calculate variance?” you’ll get some nice explanations that say:

- Calculate the mean (average) of your numbers
- Calculate the average of: each number minus the mean, squared

That’s fine for people trying to just understand how the math works, but if you are calculating variance in a computer program, you might not realize there is a way to do it in a single pass over the data.

That can be significant to the performance and even feasibility of your algorithm!

Here is how you calculate variance in one pass:

- Calculate the mean (average) of your numbers
- In the same loop, calculate the mean (average) of your numbers squared
- After the loop, variance is the absolute value of #2, minus #1 squared

That might look like word salad, so here’s a code snippet.

float Lerp(float a, float b, float t) { return a * (1.0f - t) + b * t; } float Variance_1Pass(const std::vector & data) { // get the average (value) and average (value*value) float average_value = {}; float average_valueSquared = {}; for (size_t index = 0; index < data.size(); ++index) { float value = data[index]; average_value = Lerp(average_value, value, 1.0f / float(index + 1)); average_valueSquared = Lerp(average_valueSquared, value * value, 1.0f / float(index + 1)); } // variance is absolute value of average(value*value) - (average_value*average_value) return abs(average_valueSquared - (average_value * average_value)); }

There is code that goes with this post, that implements it both ways and shows you that they are equivalent. You can find it at: https://github.com/Atrix256/CalculateVariance1Pass/blob/master/main.cpp

If you are wondering why I'm using "lerp" to average numbers, check out this post: https://blog.demofox.org/2016/08/23/incremental-averaging/

It turns out this one pass method can have numerical problems though, so no free lunch. Here is a more numerically robust way to do it, which also allows you to incrementally calculate variance, as numbers come in (Thanks Bart!): https://www.johndcook.com/blog/standard_deviation/

Why might you want to calculate variance?

One reason is if you are analyzing or reporting data, the average value is important to know, but it's also important to know if the numbers were usually pretty close to the average, or if they had lots of spikes above and below the average. You can square root variance to get the standard deviation, which is in the same units as the data you are reporting.

Assuming your data is a Gaussian distribution (due to something called the central limit theorem, a surprising number of things are actually gaussian distributed – like even rolling a bunch of dice and adding them up), 68% of the data points are + or – 1 standard deviation from the mean.

As an example, if the average temperature at your house over a month was 75 degrees Farenheit with a standard deviation of 5 degrees, that means that 68% of the days had a temperature between 70 and 80 degrees.

If the average temperature was still 75 but had a variance of 25 degrees, that means that 68% of the days had a temperature between 50 and 100 degrees. That is quite a difference! Just reporting the average temperature doesn't convey this information the same way as reporting average and standard deviation (or variance) does.

For more info on that, check this out: https://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule

Lastly, I mentioned that doing 2 passes to calculate variance could be a deal breaker for an algorithm.

An example of this is a graphics technique called "Variance Shadow Maps" (paper: http://www.punkuser.net/vsm/vsm_paper.pdf) which ultimately calculates a mean and a variance for how far a group if pixels is away from a light source. When rendering the variance shadow map from the point of the view of the light, each pixel stores the depth, as well as the depth squared. A fun property is that you can blur these values with neighboring pixels without harming the mathematical integrity of the values. The result is soft shadows. (more info on soft shadows: https://blog.demofox.org/2017/07/01/why-are-some-shadows-soft-and-other-shadows-hard/)

When lighting a pixel later on and using the shadow map, it knows the pixel's distance from the light source, and can read the two values from the filtered (blurred) shadow map, which allow it to get the mean and variance of the objects in the shadow map (the things that are casting shadows). It then uses something called Chebyshev's inequality to get an estimate for how much in shadow the pixel is.

That is a lot of setup explanation, but if having to do 2 pass variance calculations, instead of the 1 pass that it does do, you'd have to run over the full screen of pixels and do logic for each one (subtract the average pixel value), to calculate the variance. In real time graphics, having to do an extra "full screen pass" can be pretty costly, and can easily put a game over budget, meaning the technique would have to be cut so the rest of the game could render fast enough.

This blog post is here in the hopes that the next time someone googles "how do i calculate variance" for use in a computer program, that they see this post, and implement it as a single pass. Fingers crossed! 😛

Nice post, thanks a lot! How would one correctly combine mean and variances obtained (in parallel, for example using fast GPU reduction) from multiple sections of a single array using the 1-pass approach you described above?

LikeLike

I am confused!

Why you use incremental average in this case? You have your vector. So you can just sum up in the loop and divide by the size of the vector after the loop.

However, if you want to do incremental average, why do you formulate your function so complicated?

My math says the following:

average_value = (average_value*float(index)+value)/float(index+1)

Its the same, but I don’t understand the meaning of your formula. I find mine very straight forward.

The abs()-call in the return statement is not needed: average_valueSquared will always be greater or equal to average_value * average_value

LikeLike

Good point about the abs. Regarding lerp, sorry about that, that is an artifact of being in real time rendering too much. Linear interpolation is something that is available in hardware in situations like alpha blending or texture sampling, so being able to show that this works with lerp was to show the GPU could be made to do it for you in certain situations.

LikeLike