Compute a streaming mean and variance you cannot hold in memory
stream is an iterable of numbers too large to keep in a list — you may pass over it only once. Return (mean, variance) using the sample variance (divide by n - 1). Use Welford's online algorithm so a single pass with O(1) memory stays numerically stable.
For fewer than two values, return variance 0.0.
def running_mean_var(stream) -> tuple[float, float]:
# your code hereWrite the implementation.
Welford keeps a running count, mean, and sum of squared deviations M2, updated per element in one O(1)-memory pass. Sample variance is M2 / (n - 1). It avoids the naive sum(x**2) - sum(x)**2 / n, which cancels catastrophically.
- ✗Using sum of squares minus square of sum, which cancels catastrophically
- ✗Buffering the whole stream, defeating the O(1)-memory goal
- ✗Dividing by n instead of n-1 for a sample variance
- →Why does the naive two-sums formula lose precision?
- →How would you merge two independently-computed partial states?
Welford keeps n, the running mean, and M2 (the running sum of squared deviations from the current mean). Each element nudges the mean, and M2 accumulates the product of the deviations before and after that nudge.
def running_mean_var(stream):
n = 0
mean = 0.0
m2 = 0.0
for x in stream:
n += 1
delta = x - mean
mean += delta / n
m2 += delta * (x - mean)
if n < 2:
return (mean, 0.0)
return (mean, m2 / (n - 1))It is one pass and O(1) memory, and — unlike sum(x**2) - sum(x)**2 / n — it never subtracts two huge nearly-equal numbers, so it stays accurate even when the values are large and the variance is small.
