Streaming statistics done right. The algebra you discovered, formally verified.
For Robert Jacoby · Streaming algebra
You had millions of clickstream records at Cars Direct. Every hour another bucket. Every day another partition. The marketing team needed the standard deviation of session duration across the whole day, and the textbook said: average the per-hour stddevs.
The textbook was wrong. Averaging stddevs ignores the spread between the groups. Pooling the sum-of-squares without the cross-term ignores the shift in the mean. Both answers are off by tens of percent on the very first day you check them against the ground truth.
You figured it out: track three numbers per group. (n, mean, M2). That triple is sufficient — in the formal sense — for the stddev. You never need the original data again.
Welford had published the recurrence in 1962. Chan-Golub-LeVeque had published the parallel merge formula in 1979. You re-derived both in production, in PHP, twenty years before BigQuery had STDDEV_POP in the box.
You called it a "cascading aggregate." Mathematicians call it a commutative monoid. The same thing.
Three laws have to hold for the merge to be a monoid: associativity (you can group the merges any way you like), commutativity (order doesn't matter), and identity (merging with the empty aggregate is a no-op). All three hold to machine epsilon, and all three are kernel-checked in Lean 4.
Your production system, rebuilt and running live in the browser. Eight thousand simulated clickstream events, partitioned into twenty-four hourly buckets, then merged bottom-up into a single day-level aggregate. The running stddev as the cascade progresses is the gold line; it lands on the ground-truth dashed line at the last step, exactly.
You can shard the events any way you like — by hour, by region, by shard ID — and the merge gives the same answer as a single-pass replay over the raw data. That is what associativity buys you. It is what makes MapReduce, Spark, ClickHouse, and BigQuery possible.
parallel split [1..5]+[6..10] vs serial [1..10] → identical to the bit
We pick three consecutive non-empty hourly buckets and verify each of the monoid laws against them. Every dot on the chart should sit at machine zero. If any one of them lifted off the floor, the algebra would be a lie and the cascade would not commute.
The textbook one-pass formula is (Σ x² − n · mean²) / (n − 1). It is mathematically correct and numerically catastrophic: when the data has a large offset, the two terms become nearly equal and the subtraction loses every bit of precision.
Welford's recurrence avoids the cancellation by tracking the running mean and updating M2 against the deviation from that mean. On the chart, the textbook formula blows up by twelve orders of magnitude as the offset grows. Welford stays flat at machine epsilon.
You didn't know it had been published. It had.
The keystone identity — that updating an aggregate with one new value equals merging it with a singleton — is . Stated formally: ∀ (s : MomentState) (x : ℝ), s.count ≠ 0 → update s x = merge s (singleton x).