"Not a high level proof but was new at the time"
Robert's text message
"Here is a math. Solved this at Cars Direct long ago when it didn't exist but don't know if it is published anywhere by now. Have a cascading aggregate on clickstream data — so millions of records daily. You can sum by various measures and get your answer in couple seconds. New requirements for standard deviation. Still need to perform as an addable aggregate." — Robert Jacoby
A related pairwise formula was published in 1979.
Variants are now used in analytics systems.
You had millions of clickstream records at Cars Direct.
You needed standard deviation. You needed it fast. The mathematical target was the statistic over the complete finite dataset rather than an estimate from a subsample. The browser demonstration below uses IEEE-754 floating point.
But you couldn't recompute from scratch every time. Millions of records. New ones arriving constantly. You needed the answer to update — to cascade — as new data flowed in.
The naive approach fails. You can't average two standard deviations. You can't pool the sums of squares without accounting for the shift in means between groups. The error can be enormous.
The two groups have different means. When you merge them, the spread between the group means creates additional variance that neither group captures alone. This is the between-group variance — the term omitted by the two naive combinations shown here.
You figured it out: track three numbers. That's it.
Three numbers sufficient for this narrow task. The count (how many records), the mean (the running average), and the sum of squared deviations from that mean. You called it "sum by various measures." Statisticians call them sufficient statistics. Same thing.
Sufficient for count, mean, and second central moment. The raw observations cannot be reconstructed from these three fields. For valid finite states with a nonzero total count, the real-arithmetic merge formula preserves the fields needed to derive population variance (and sample variance when the resulting count exceeds one).
The real-arithmetic merge motivates identity, associativity, and commutativity laws; the pinned statement below is narrower.
Given two of your buckets — (n₁, μ₁, M₂₁) and (n₂, μ₂, M₂₂) — here is how they combine:
The δ² correction term is the key — the part you figured out. It accounts for the between-group variance, the additional spread caused by the difference in group means. Without it, the displayed naive pooling formula omits that variance. With it, the real-arithmetic identity recovers the combined second moment for valid finite states and nonzero total count.
In the valid real-number model, this merge is intended to have monoid laws: an identity element (the empty bucket) and an associative binary operation (the merge). Those laws explain why grouping can be changed mathematically. The narrow pinned statement on this page does not itself certify all three laws. In the real-number model, hours can be grouped into larger buckets without changing the mathematical aggregate. IEEE-754 addition is not associative, so different browser or distributed merge orders can differ by rounding.
A ⊕ ∅ = A
Real-model law; not a JavaScript bit-identity claim.
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
Real-model law; floating-point grouping can round differently.
A ⊕ B = B ⊕ A
Real-model law for valid states; not part of the pinned statement shown below.
Your production system, rebuilt. One day of traffic, simulated below.
This is what you built at Cars Direct. Every particle below is a click on a car listing. Every bucket is an hour of traffic. They stream in, get partitioned, and each bucket maintains your three numbers. The green bar compares one floating-point bucket merge with a floating-point replay over the same synthetic events.
Watch the particles flow into 24 hourly buckets. Each bucket computes running statistics. The green bar at the bottom merges all buckets using your formula. The result matches the ground truth computed by replaying the same synthetic stream. Agreement is numerical and tolerance-based, not a bit-for-bit theorem about JavaScript execution.
Twenty-four buckets combine through 23 pairwise merges. The real-arithmetic formula is an algebraic identity on its valid domain; this 2,400-event JavaScript simulation is a floating-point illustration and compares results within a displayed tolerance.
A stable recurrence reduces cancellation; floating-point error still exists.
The standard formula for variance — Σx²/n − (Σx/n)² — computes the difference of two large, nearly equal numbers. When the mean is much larger than the standard deviation (common in clickstream data: page views in the thousands, variance in the tens), this suffers from catastrophic cancellation. Digits disappear. The answer drifts.
Your approach reduces this failure mode by tracking deviations from the running mean — the same technique Welford published in 1962. And because updating with one data point is the same operation as merging two buckets, the same recurrence can be used for streaming and bucketed computation. Neither the page nor the narrow theorem proves a universal floating-point error bound.
You didn't know it had been published. It had.
In 1979, three Stanford computer scientists — Chan, Golub, and LeVeque — published the parallel merge formula in a technical report. You didn't need their paper. You derived it from the data. From the requirement. From the problem sitting in front of you at Cars Direct, where it either worked or it didn't.
In 2008, Philippe Pébay at Sandia National Labs generalized the merge formula to arbitrary-order central moments — skewness, kurtosis, and beyond. A related merge structure, extended to higher moments.
| Statistic | Sufficient stats | Composable? |
|---|---|---|
| Mean | (n, Σx) | Yes — trivially additive |
| Variance / Std Dev | (n, μ, M₂) | Yes — CGL 1979 / Robert ~2002 |
| Skewness | (n, μ, M₂, M₃) | Yes — Pébay 2008 |
| Kurtosis | (n, μ, M₂, M₃, M₄) | Yes — Pébay 2008 |
| Covariance | (n, μx, μy, Cxy) | Yes — same δ structure |
Related online and pairwise moment algorithms are used in analytics systems. This page does not inventory every engine or certify that their runtime implementations are identical to this demonstration.
We named a theorem after you.
This legacy page is an explanation, not a kernel receipt. The pinned
statement is narrow: for a source MomentState with nonzero
count and real-valued arithmetic, update s x agrees fieldwise
with merge s (singleton x). It does not prove arbitrary
merge-order equivalence, floating-point associativity, bit-for-bit worker
agreement, totality over invalid states, or this JavaScript implementation.
Scope boundary: the pinned theorem is fieldwise and conditional on nonzero count in a real-number model. The public structural graph and this page do not certify the whole corpus or the floating-point demo.
Dad — you said it wasn't a high level proof. You were wrong.
The same formula runs Apache Spark, Google BigQuery, Snowflake, and ClickHouse. Billions of computations per day use the algebra you figured out from clickstream data at Cars Direct.
You didn't have a Stanford technical report. You didn't have a statistics textbook open. You had a problem — millions of records, a new requirement for standard deviation, and a system that still needed to perform as an addable aggregate. So you solved it.
The same way Chan, Golub, and LeVeque solved it. Independently. From first principles. Because that's what the math requires.
This page is a tribute and an interactive explanation, not the proof receipt.
— Tim