A large input is folded a piece at a time and each piece reports its own variance. Which quantities must a piece carry instead so the pieces combine exactly?

middleshould knowfreq 45%

answer

each piece measures around its own mean
the gap between piece means is lost
carry count, mean, squared deviations
apply the divisor convention once

basics

~20 s

Each piece must carry three things: its count, its mean, and its summed squared deviations from that mean. Variances cannot be averaged because each is measured around a different origin, and the merge has to add back the gap between those origins.

solid answer

~50 s

A variance measures spread around a mean, and each piece measures around its own mean. Averaging the piece variances silently discards how far apart those means were: two pieces of a thousand constant values, all 10 in one and all 20 in the other, each have variance zero and combine to a variance of 25. So a piece carries (n, mean, m2), where m2 is the sum of squared deviations from its own mean. Two of them combine as n = n_a + n_b, delta = mean_b - mean_a, mean = mean_a + delta * n_b / n, and m2 = m2_a + m2_b + delta * delta * n_a * n_b / n - that last term is the between-piece spread the naive average threw away. Divide once at the end, by n or by n - 1 depending on the convention you want.

A variance measures spread around a mean, and each piece measures around **its own** mean. Averaging the piece variances silently discards how far apart those means were: two pieces of a thousand constant values, all 10 in one and all 20 in the other, each have variance zero and combine to a variance of 25. So a piece carries `(n, mean, m2)`, where `m2` is the sum of squared deviations from its own mean. Two of them combine as `n = n_a + n_b`, `delta = mean_b - mean_a`, `mean = mean_a + delta * n_b / n`, and `m2 = m2_a + m2_b + delta * delta * n_a * n_b / n` - that last term is the between-piece spread the naive average threw away. Divide once at the end, by `n` or by `n - 1` depending on the convention you want.

code

pseudocode · 17 lines

pseudocode

combine(a, b):
    if a.n == 0: return b
    if b.n == 0: return a

    n     = a.n + b.n
    delta = b.mean - a.mean
    mean  = a.mean + delta * (b.n / n)
    m2    = a.m2 + b.m2 + delta * delta * (a.n * b.n / n)

    return (n, mean, m2)

state = (0, 0.0, 0.0)
for each piece:
    state = combine(state, triple_of(piece))

spread_population = state.m2 / state.n
spread_sample     = state.m2 / (state.n - 1)

go deeper

for a junior

Know that spread is measured around a mean and that each piece measures around its own. That single fact already explains why the pieces' variances cannot be averaged into the input's variance.

for a middle

Explain the carried triple - count, mean, summed squared deviations - and show the combine, including the term built from the gap between the two piece means. Say why the divisor is applied once, at the end.

for a senior

Demonstrate that the totals-of-squares form merges but cancels: name the loss of significant digits when values are large and clustered, the negative result that betrays it, and the offset trick that avoids it.

for a principal

The rule worth owning across a team is that per-piece steps publish combinable state, not finished statistics. Without it, re-cutting an input into different pieces silently changes a number somebody already reported.

Why variances do not average

Variance is the mean squared distance of the values from their mean. The phrase their mean is the whole problem. When an input is folded a piece at a time, each piece computes distances from the origin it happened to see, and two pieces with different means measured from two different origins. Averaging those two numbers keeps the spread inside each piece and throws away the spread between them.

The cleanest demonstration uses pieces with no internal spread at all:

Piece A: one thousand values, every one of them 10. Variance 0.
Piece B: one thousand values, every one of them 20. Variance 0.
The two thousand values together: mean 15, every value five away from it, variance 25.

The average of the piece variances is 0. The truth is 25. No amount of arithmetic on the two zeros recovers it, because the information that distinguished the pieces - that their means differed by ten - was discarded the moment each piece reported a finished statistic.

The quantity that does combine

What combines is not the variance but the summed squared deviations, usually written m2: for a piece, the sum over its values of (value - piece_mean) squared. A piece therefore carries a triple:

carried	what it is	why the merge needs it
`n`	values counted in this piece	weights the two sides, and is the final divisor
`mean`	this piece's mean	its distance from the other piece's mean is the missing spread
`m2`	summed squared deviations from that mean	the additive part of the spread

And two triples merge as:

n = n_a + n_b
delta = mean_b - mean_a
mean = mean_a + delta * n_b / n
m2 = m2_a + m2_b + delta * delta * n_a * n_b / n

Step 4 is the one people leave out. Its term is the between-piece spread: zero when the two pieces had the same mean, and dominant when they did not. Check it against the demonstration above - delta is 10, n_a * n_b / n is 500, so the merged m2 is 0 + 0 + 100 * 500 = 50,000, and 50,000 / 2000 is exactly the 25 we wanted.

The merge is order-independent and pairwise, so it works the same whether you fold pieces one after another into a running triple or combine partial triples in any grouping you like. The state carried between pieces is three numbers whatever the input's length, so the pass stays bounded.

The shortcut that merges but is not safe

Algebraically, the summed squared deviations can also be reached from a running total and a running total of squares: m2 = sum_of_squares - total * total / n. That triple - (n, total, sum_of_squares) - also merges by plain addition, and it is genuinely tempting because each piece needs only two additions.

The problem is numeric rather than algebraic. When the values are large and tightly clustered - timestamps counted in seconds, prices around a million, sensor readings offset by a big constant - sum_of_squares and total * total / n are both enormous and nearly equal, and subtracting two nearly equal large numbers cancels away the leading digits. The result can lose most of its significant figures, and in the worst case comes back slightly negative, which is impossible for a sum of squares and is the tell that this is what happened. The (n, mean, m2) triple never forms those two huge quantities at all, so it does not cancel. Prefer it, and if you must use the totals form, subtract a rough offset from every value first so the numbers being squared are small.

Applying the convention exactly once

The divisor is a separate decision from the merge. Dividing m2 by n gives one convention; dividing by n - 1 gives the other, and tools differ in which they hand you by default and in how they let you ask for the other. None of that touches the fold: the fold accumulates m2 and n, and the convention is applied once, at the end, on the merged pair. The real bug here is applying it twice - taking a piece's already-adjusted variance, multiplying back up by the wrong count to recover m2, and ending up with a value that is off by a factor that shrinks as the pieces get bigger.

The same shape, one step further

Covariance between two columns carries the count, both means, and the summed products of the two columns' deviations; the merge adds a cross term built from both gaps, delta_x * delta_y * n_a * n_b / n.
Anything standardised - a coefficient built from a variance, a spread-scaled score - is the variance problem wearing a different name, and needs the same triple carried underneath rather than the finished ratio.
Per-key spread carries one triple per key, and the merge above runs per key.

Where designs differ

Some tools expose only the finished statistic from a per-piece aggregate, in which case you compute the triple yourself from the piece's values; others expose the intermediate state, or an explicit combine for it, and then the fold is theirs rather than yours. The arithmetic is identical either way. What you must not do is assume the finished statistic is enough, because the field that would have told you how far the piece's mean sat from everyone else's is precisely the one the finished statistic dropped.

## Why variances do not average Variance is the mean squared distance of the values from **their** mean. The phrase *their mean* is the whole problem. When an input is folded a piece at a time, each piece computes distances from the origin it happened to see, and two pieces with different means measured from two different origins. Averaging those two numbers keeps the spread **inside** each piece and throws away the spread **between** them. The cleanest demonstration uses pieces with no internal spread at all: - Piece A: one thousand values, every one of them `10`. Variance `0`. - Piece B: one thousand values, every one of them `20`. Variance `0`. - The two thousand values together: mean `15`, every value five away from it, variance `25`. The average of the piece variances is `0`. The truth is `25`. No amount of arithmetic on the two zeros recovers it, because the information that distinguished the pieces - that their means differed by ten - was discarded the moment each piece reported a finished statistic. ## The quantity that does combine What combines is not the variance but the **summed squared deviations**, usually written `m2`: for a piece, the sum over its values of `(value - piece_mean)` squared. A piece therefore carries a triple: | carried | what it is | why the merge needs it | |---|---|---| | `n` | values counted in this piece | weights the two sides, and is the final divisor | | `mean` | this piece's mean | its distance from the other piece's mean is the missing spread | | `m2` | summed squared deviations from that mean | the additive part of the spread | And two triples merge as: 1. `n = n_a + n_b` 2. `delta = mean_b - mean_a` 3. `mean = mean_a + delta * n_b / n` 4. `m2 = m2_a + m2_b + delta * delta * n_a * n_b / n` Step 4 is the one people leave out. Its term is the between-piece spread: zero when the two pieces had the same mean, and dominant when they did not. Check it against the demonstration above - `delta` is `10`, `n_a * n_b / n` is `500`, so the merged `m2` is `0 + 0 + 100 * 500 = 50,000`, and `50,000 / 2000` is exactly the `25` we wanted. The merge is order-independent and pairwise, so it works the same whether you fold pieces one after another into a running triple or combine partial triples in any grouping you like. The state carried between pieces is three numbers whatever the input's length, so the pass stays bounded. ## The shortcut that merges but is not safe Algebraically, the summed squared deviations can also be reached from a running total and a running total of squares: `m2 = sum_of_squares - total * total / n`. That triple - `(n, total, sum_of_squares)` - also merges by plain addition, and it is genuinely tempting because each piece needs only two additions. The problem is numeric rather than algebraic. When the values are large and tightly clustered - timestamps counted in seconds, prices around a million, sensor readings offset by a big constant - `sum_of_squares` and `total * total / n` are both enormous and nearly equal, and subtracting two nearly equal large numbers **cancels away the leading digits**. The result can lose most of its significant figures, and in the worst case comes back slightly negative, which is impossible for a sum of squares and is the tell that this is what happened. The `(n, mean, m2)` triple never forms those two huge quantities at all, so it does not cancel. Prefer it, and if you must use the totals form, subtract a rough offset from every value first so the numbers being squared are small. ## Applying the convention exactly once The divisor is a separate decision from the merge. Dividing `m2` by `n` gives one convention; dividing by `n - 1` gives the other, and tools differ in which they hand you by default and in how they let you ask for the other. None of that touches the fold: the fold accumulates `m2` and `n`, and the convention is applied once, at the end, on the merged pair. The real bug here is applying it twice - taking a piece's already-adjusted variance, multiplying back up by the wrong count to recover `m2`, and ending up with a value that is off by a factor that shrinks as the pieces get bigger. ## The same shape, one step further - **Covariance between two columns** carries the count, both means, and the summed products of the two columns' deviations; the merge adds a cross term built from both gaps, `delta_x * delta_y * n_a * n_b / n`. - **Anything standardised** - a coefficient built from a variance, a spread-scaled score - is the variance problem wearing a different name, and needs the same triple carried underneath rather than the finished ratio. - **Per-key spread** carries one triple per key, and the merge above runs per key. ## Where designs differ Some tools expose only the finished statistic from a per-piece aggregate, in which case you compute the triple yourself from the piece's values; others expose the intermediate state, or an explicit combine for it, and then the fold is theirs rather than yours. The arithmetic is identical either way. What you must not do is assume the finished statistic is enough, because the field that would have told you how far the piece's mean sat from everyone else's is precisely the one the finished statistic dropped.

Two pieces have identical variances but different means. What does the combined variance do?
It comes out larger than either, because the distance between the two origins is itself variation. The merge adds `delta * delta * n_a * n_b / n` to the summed squared deviations, where `delta` is the gap between the piece means. Two thousand-value pieces that are internally constant at 10 and at 20 each have spread zero and combine to a variance of 25.
What must a piece carry so that a covariance between two of its columns can be combined the same way?
The count, the mean of each column, and the summed products of the two columns' deviations from those means. The merge adds the two sides' summed products plus a cross term `delta_x * delta_y * n_a * n_b / n`, built from both gaps. As with the single-column case, the finished ratio is useless to a fold; only the unnormalised sums combine.
Does the choice between dividing by the count and by the count minus one affect the merge itself?
No. The fold accumulates summed squared deviations and a count, both of which combine without reference to any convention, and the single division happens once at the end. The bug to watch for is applying the convention inside each piece and again at the end, which leaves the result off by a factor that quietly shrinks as pieces get larger.

saying these in an interview costs you the question

Averages the piece variances and calls it the input's variance
Carries the finished statistic rather than the unnormalised sums
Derives spread from a total and a total of squares without a count
Assumes the squared-total shortcut is numerically safe at any magnitude
Applies the divisor convention inside each piece and again at the end
Insists a computed variance can never come back negative

A large input is folded a piece at a time and each piece reports its own variance. Which quantities must a piece carry instead so the pieces combine exactly?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~5 min

Why variances do not average

The quantity that does combine

The shortcut that merges but is not safe

Applying the convention exactly once

The same shape, one step further

Where designs differ

▾common follow-ups3 questions

▾red flags6 flags

Why variances do not average

The quantity that does combine

The shortcut that merges but is not safe

Applying the convention exactly once

The same shape, one step further

Where designs differ

answer

go deeper