Numerical Stability of Single-Pass Variance

1. The Variance Formula: A Hidden Subtraction

Let's recall the "textbook" or "shortcut" single-pass formula for variance we derived in our first lesson:

${\sigma }^2=\mathbb{E}[X^2]-(\mathbb{E}[X]{)}^2$

Based on our last lesson, your alarm bells should be ringing. This formula contains a subtraction. For this to be a site of catastrophic cancellation, the two terms being subtracted, $\mathbb{E}[X^2]$ and $(\mathbb{E}[X]{)}^2$, must be nearly equal.

But under what conditions does this happen? The following reading explains it perfectly.

The article states that the problem occurs when the variance is very small and the mean is very large. Let's prove this mathematically. It's a simple but crucial derivation.

We know the definitional formula for variance is ${\sigma }^2=\mathbb{E}[(X-\mu {)}^2]$, where $\mu =\mathbb{E}[X]$. Let's expand this:

1. ${\sigma }^2=\mathbb{E}[X^2-2X\mu +{\mu }^2]$
2. Using the linearity of expectation: ${\sigma }^2=\mathbb{E}[X^2]-\mathbb{E}[2X\mu ]+\mathbb{E}[{\mu }^2]$
3. Since $\mu$ is a constant: ${\sigma }^2=\mathbb{E}[X^2]-2\mu \mathbb{E}[X]+{\mu }^2$
4. Substituting $\mu =\mathbb{E}[X]$: ${\sigma }^2=\mathbb{E}[X^2]-2{\mu }^2+{\mu }^2$
5. This simplifies to: ${\sigma }^2=\mathbb{E}[X^2]-{\mu }^2$, which is our single-pass formula.

Now, let's rearrange this slightly:
$\mathbb{E}[X^2]={\sigma }^2+{\mu }^2$

This tells us exactly what the two terms in the variance formula are. The single-pass formula is effectively computing:
$({\sigma }^2+{\mu }^2)-{\mu }^2$

Now you can see the problem clearly. If the variance ${\sigma }^2$ is very small compared to the mean-squared ${\mu }^2$, then ${\sigma }^2+{\mu }^2$ is a number that is very close to ${\mu }^2$. We are subtracting two nearly equal, large numbers—the exact recipe for catastrophic cancellation.

2. A Practical Demonstration of Failure

Let's see this in action. The following resource provides a simple, devastating example.

Let's break down the example from the notes.

• Dataset 1: x = {1, 2, ..., 10}.

  • Mean $\mu =5.5$, Variance ${\sigma }^2=8.25$ (for population variance).
  • Here, ${\mu }^2=30.25$ is not drastically larger than ${\sigma }^2$. The subtraction is fine.
  • mean(x^2) - mean(x)^2 works and gives 8.25.

• Dataset 2: x = {10⁹ + 1, 10⁹ + 2, ..., 10⁹ + 10}.

  • The variance is unchanged: ${\sigma }^2=8.25$.
  • The mean is huge: $\mu =10^9+5.5$.
  • Now, ${\mu }^2\approx (10^9{)}^2=10^{18}$.
  • The computer needs to calculate $\mathbb{E}[X^2]={\sigma }^2+{\mu }^2=8.25+(10^9+5.5{)}^2$.

A standard double precision floating-point number has about 15-16 significant decimal digits. The term ${\mu }^2$ is a number around $10^{18}$. To represent $8.25+10^{18}$, you'd need to store a number like 1,000,000,000,000,000,008.25.... This requires more precision than is available.

The 8.25 part (which represents all the information about the variance!) is completely lost when it's added to the enormous $10^{18}$ term. This is an example of the "swamping" we discussed in the last lesson. The computer ends up storing a value for $\mathbb{E}[X^2]$ that is indistinguishable from its stored value for ${\mu }^2$. The subsequent subtraction mean(x^2) - mean(x)^2 yields 0 or some other small, meaningless number that is pure computational noise.

This instability is not just a theoretical curiosity; it's a very practical problem.

3. A Glimpse of a Solution: The Data Shift Trick

Since the problem is caused by a large mean, what if we could somehow make the mean smaller before the calculation? It turns out we can. Shifting all data points by a constant value does not change the variance.

The article "One-Pass Naive Algorithm for Computing Variance" describes this simple but effective workaround.

The data shift trick—subtracting the first data point (or any other constant) from all values—effectively computes the variance on a new dataset whose mean is close to zero. This neatly sidesteps the catastrophic cancellation problem. While clever, this still requires you to know a value from the dataset beforehand, which isn't always ideal for true streaming applications. This observation beautifully sets the stage for Welford's algorithm, which we'll see accomplishes a similar stabilization but in a running, online fashion.

Conclusion

This lesson closes our investigation into why common statistical algorithms can fail.

Key Takeaways:

• The single-pass variance formula, ${\sigma }^2=\mathbb{E}[X^2]-(\mathbb{E}[X]{)}^2$, is vulnerable to catastrophic cancellation.
• The instability occurs when the variance (${\sigma }^2$) is small relative to the square of the mean (${\mu }^2$).
• In this scenario, $\mathbb{E}[X^2]$ and $(\mathbb{E}[X]{)}^2$ become two large, nearly-equal numbers. The information about the variance is contained in the tiny difference between them, which is wiped out by floating-point inaccuracies during the subtraction.
• This problem is not theoretical; it happens in practice with common datasets that have a large offset from the origin.

Preview of the Next Module:

We have now thoroughly explored the problem. We derived the naive formula, benchmarked it against a stable two-pass method, and diagnosed its failure as a case of catastrophic cancellation.

The next module, "Welford's Algorithm: Derivation and Properties," will finally introduce the solution. In our next lesson, we will begin by deriving the recursive update rules for the mean and the sum of squared differences that are at the heart of Welford's elegant and numerically stable one-pass algorithm.