Two-Pass Variance Calculation

1. Revisiting the Definition: The Two-Pass Approach

Let's start by recalling the definitional formula for population variance (${\sigma }^2$) for a dataset $\{x_1,...,x_N\}$:

${\sigma }^2=\frac{1}{N}{\sum }_{i=1}^N(x_i-\mu {)}^2\text{where}\mu =\frac{1}{N}{\sum }_{i=1}^N{x}_i$

A direct, literal implementation of this formula requires two distinct steps, or "passes," over the data:

1. First Pass: Iterate through all the data points to compute their sum, $\sum x_i$, and then calculate the mean, $\mu$.
2. Second Pass: Iterate through all the data points a second time. In this pass, for each point $x_i$, you calculate the squared difference $(x_i-\mu {)}^2$ and add it to a running total. Finally, you divide this sum by $N$.

This method is straightforward and easy to understand as it directly follows the mathematical definition.

To see this formalized, let's turn to a clear description from Wikipedia.

As you can see, the logic is simple: compute the mean, then compute the sum of squared differences from that mean. The main drawback appears to be efficiency—you have to read your data twice. This can be costly if the data is very large and not stored in memory.

2. The Two-Pass Algorithm as a Stable Baseline

If the two-pass algorithm is less efficient, why do we care about it? Because it is numerically stable. It serves as a reliable benchmark for accuracy against which other algorithms are measured.

The stability comes from the fact that in the second pass, you are calculating differences from the true mean of the sample ($x_i-\mu$). The magnitudes of these intermediate values $(x_i-\mu )$ are generally much smaller than the magnitudes of the original data points $x_i$. This prevents a specific type of floating-point error that we will discuss in the next lesson.

A research paper from the SIGMOD Record provides an excellent overview of the practical performance and precision of various variance algorithms.

The key takeaway from the paper is that across their experiments, the two-pass algorithm consistently delivered the most accurate results. The empirical evidence in Figures 2a and 2b is compelling: as the data becomes more challenging (by adding a large constant "shift" or by increasing the dataset size), the precision of other algorithms degrades, while the two-pass method remains highly accurate. This is why it's considered a stable baseline.

3. A Concrete Example of Stability

Let's make this abstract idea of stability more concrete. What does it look like when an algorithm is unstable? The Wikipedia article you read earlier provides a perfect example.

As the example shows, variance is invariant to shifting; adding a constant to every data point does not change the spread of the data, so the variance should remain the same. The two-pass algorithm correctly computes the variance as 30 in all cases.

However, the single-pass "textbook" algorithm we derived last lesson starts to lose precision and eventually fails spectacularly, producing a negative variance. This is mathematically impossible and highlights a critical flaw in how the single-pass formula behaves when implemented on a computer with finite-precision arithmetic. This type of error is known as catastrophic cancellation, a topic we will dissect in our next lesson.

Conclusion

In this lesson, we have formally described the two-pass algorithm for variance and established why it's considered a stable baseline.

Key Takeaways:

• The two-pass algorithm is a direct implementation of the definitional formula for variance, requiring one pass to compute the mean and a second pass to compute the sum of squared differences from that mean.
• Its primary advantage is numerical stability. By computing differences from the sample's true mean, it avoids working with large intermediate values that can lead to significant floating-point errors.
• Empirical evidence and concrete examples show that it produces accurate results even for datasets that cause the single-pass "textbook" formula to fail.
• Its main disadvantage is the need to access the data twice, which can be inefficient for out-of-memory datasets or data streams.

We now have two competing algorithms: a fast but potentially unstable single-pass method, and a stable but potentially slow two-pass method. This sets up the perfect motivation for Welford's algorithm, which aims to give us the best of both worlds: single-pass efficiency and numerical stability.

Preview of the Next Lesson:

To fully appreciate why Welford's algorithm is needed, we must first understand the enemy. In the next lesson, we will dive into the concept of catastrophic cancellation, the specific floating-point arithmetic issue that causes the textbook single-pass formula to fail so dramatically.