When you want to compute the mean and variance for a large data set that cannot fit into memory, the solution is to use an incremental (also called online or streaming) algorithm. For this purpose, we use Welford’s method, which is efficient, numerically stable, and relatively simple to implement.
Suppose you have a sequence of data points x1, x2, …, xn, and you want to compute the mean and variance of this large dataset. Let’s denote the mean after k data points as μk and the kth partial variance as M2, k.
We will iterate over the data points one by one and update the mean and variance terms as we go using the following equations:
μ0 = 0
M2, 0 = 0
For each data point xk + 1, we update our estimates using:
Δk = xk + 1 − μk
$$\mu_{k+1} = \mu_k + \frac{\Delta k}{k+1}$$
Δk′ = xk + 1 − μk + 1
M2, k + 1 = M2, k + Δk ⋅ Δk′
After processing all the data points, we have:
$$\text{Mean: } \bar{x_n} = \mu_n$$
$$\text{Variance: } \sigma^2_n = \frac{M_{2,n}}{n} \quad \text{(for sample variance)}$$
Now, let’s go through a quick example. Suppose we have a data set {1, 2, 3, 4}, but assume it can’t fit into memory. Using Welford’s method, we would perform the following...
1. Initialize μ0 = 0 and M2, 0 = 0
2. Process x1 = 1:
Δ0 = 1 − 0 = 1
$$\mu_1 = 0 + \frac{1}{1} = 1$$
Δ1′ = 1 − 1 = 0
M2, 1 = 0 + 1 ⋅ 0 = 0
3. Process x2 = 2:
Δ1 = 2 − 1 = 1
$$\mu_2 = 1 + \frac{1}{2} = 1.5$$
Δ1′ = 2 − 1.5 = 0.5
M2, 2 = 0 + 1 ⋅ 0.5 = 0.5
4. Process x3 = 3:
Δ2 = 3 − 1.5 = 1.5
$$\mu_3 = 1.5 + \frac{1.5}{3} = 2$$
Δ2′ = 3 − 2 = 1
M2, 3 = 0.5 + 1.5 ⋅ 1 = 2
5. Process x4 = 4:
Δ3 = 4 − 2 = 2
$$\mu_4 = 2 + \frac{2}{4} = 2.5$$
Δ3′ = 4 − 2.5 = 1.5
M2, 4 = 2 + 2 ⋅ 1.5 = 5
6. Compute final mean and variance:
Mean: x̄ = μ4 = 2.5
$$\text{Sample Variance: } \sigma^2 = \frac{M_{2,4}}{4} = \frac{5}{4} = 1.25$$
To wrap up, Welford’s method allows us to incrementally calculate the mean and variance for large data sets that cannot fit into memory by processing each data point one at a time and updating our estimates accordingly. This method is both efficient and numerically stable.