Motivation
A data set can be large in two distinct ways. It may contain too many observations to fit in memory, or it may arrive continuously so that there is never a convenient moment to load the whole collection. In both situations, a familiar formula can hide an unsuitable algorithm. The expression for an average uses every observation, but computing the average does not require retaining them all. The useful question is which information must survive after a block has been processed.
Suppose a sensor produces a sequence of real measurements. We want its mean and variability, and later want to combine the results from several machines. Saving only each machine's average is insufficient when the machines process different numbers of records. Saving only averages and variances without counts is insufficient for the same reason. A suitable summary must have enough information to account for both variation within a block and displacement between block averages.
There is also a numerical issue. If all observations are near a large offset, the variance can be tiny compared with their squares. Subtracting two large, nearly equal floating-point quantities can erase the information we wanted. Algebraic equivalence over the real numbers therefore does not guarantee comparable computational accuracy. This unit develops exact identities first, then explains what those identities do and do not promise in finite precision.
Definitions
Definition 1.1.1
(Block summary)
For a nonempty finite block of real numbers, define its count, mean and centered sum of squares by
The summary of is the triple .
The descriptive population variance of these records is . If the records are independent identically distributed observations from a distribution with finite variance and , the unbiased sample variance is . These are different quantities with different denominators. Without the sampling assumptions, the second expression remains a computable descriptive statistic but its unbiasedness interpretation has not been justified.
A streaming algorithm examines records sequentially while retaining a state whose size does not grow with the number of records. Our state contains one integer count and two real accumulators. Calling this constant memory uses a fixed-width arithmetic model: an exact integer count for arbitrarily long streams needs a growing number of bits. In an actual implementation, count overflow must be considered separately from floating-point roundoff.
Definition 1.1.2
(Block reduction)
A block reduction partitions the records into disjoint blocks, computes a summary for each block, and then combines the summaries by repeated binary merges along a merge tree whose leaves are the blocks. An empty block has count zero and is handled as an identity: merging it with another summary returns the other summary.
The mean of an empty block need not be assigned a mathematical value. Defining it as zero and then applying a formula that divides by the total count would create an avoidable special-case error when both inputs are empty.
We analyze exact real arithmetic unless roundoff is explicitly discussed. A floating-point operation rounds its exact result to a representable number. Relative-error models are useful away from overflow and underflow, but they do not make subtraction of nearly equal quantities well conditioned. Moreover, the decimal input may already have lost detail when converted to binary floating point; no variance recurrence can reconstruct information absent from the stored records.
Theorem/proposition
Proposition 1.1.3
(Adding one observation)
Let summarize a nonempty block and append . Set . Then the exact summary of the enlarged block is
The initial one-record summary is . Equivalently, the increment of is , which is nonnegative.
Theorem 1.1.4
(Merging two nonempty blocks)
Let disjoint blocks have summaries and , with . Put and . Their concatenation has summary
In exact arithmetic, repeated merging returns the summary of the full multiset regardless of the merge tree or input ordering.
Concept lensAlgebraic
The summary in additive coordinates
A nonempty summary determines, and is determined by, the power sums , where and . Power sums of disjoint blocks simply add, so in these coordinates the merge is vector addition, and associativity, commutativity and the empty identity are immediate. The merge theorem is this addition rewritten in the coordinates . The two descriptions agree in exact arithmetic; in floating point the centered coordinates are preferred because recovering is the cancellation shown in the large-offset example.
Proof sketch or proof idea
Proof
(Splitting each deviation at the block mean)
The weighted-mean identity follows directly by adding block sums: , so . For the centered sum, write each deviation in block as . On squaring and summing, the cross term vanishes because the deviations from sum to zero. Thus the contribution of this block is . The analogous contribution from block is . Since and , the two displacement contributions add to
For the final assertion, induct on a merge tree whose leaves are disjoint nonempty blocks. Each leaf holds the exact summary of its block. If the two children of a node hold the exact summaries of the disjoint unions of their leaves, the merge formula gives the exact summary of the union of all leaves below the node. Hence the root holds the summary of the full multiset. That summary depends only on the multiset, so neither the tree shape nor the order of the leaves can change it.
Proof
(Appending a one-record block)
Appending means merging with a block for which , and , so and . The merge formula gives and . Also , so , which proves the alternative form of the recurrence. That alternative avoids forming a large raw square of an observation.
Proof X-ray
Where exactness and disjointness enter
The one non-obvious move is to split each deviation from the combined mean at the block mean. The cross term then vanishes because is exactly the mean of block ; this is where nonemptiness is needed, since an empty block has no mean to split at. Disjointness is used when the centered sum of the concatenation is written as a sum over plus a sum over : every record is counted once. The tree induction then closes because each internal node receives exact summaries of disjoint leaf sets. In floating point the inductive hypothesis fails at the first rounded merge, so tree-independence is not inherited: a deterministic tree makes a computation reproducible without making it exact.
The identity also explains why averaging block variances fails: variation between the block means contributes to the combined spread, and that contribution is nonnegative in exact arithmetic.
Counterexample mode
Equal block sizes do not make block variances averageable
Claim: if two blocks have the same size, the combined descriptive variance is the average of the block descriptive variances. Take and . Both blocks have centered sum and variance , so the average is . The merge gives , and , so the combined variance is ; directly, the deviations from the mean are . Dividing the merge formula by gives the correct statement for : the combined variance equals the average of the block variances plus . The claim holds only when the block means coincide.
Worked examples
Worked example 1.1.5
(Unequal blocks: check every piece of the summary)
Take and . Their summaries are and . Here and , so the merged mean is . The centered sum is . Thus the descriptive variance is , and the sample variance is when the sampling interpretation is appropriate.
Direct inspection confirms the result: the deviations from are , whose squared values sum to . The unweighted average of the block means would be , already wrong before we ask about variance. The average of the block descriptive variances would also omit the large displacement between the two groups.
Worked example 1.1.6
(A large offset and a small spread)
Consider . The mean is , the centered sum is , and the descriptive variance is . The exact identity
subtracts quantities of order to recover a number of order one. In a straightforward binary64 calculation with left-to-right summation, this raw-moment expression can return for these records. This is a concrete evaluation result, not a universal specification of every language, compiler or summation library.
The centered update instead encounters differences on the scale of the spread. Its successive states have means , , and , and centered sums , , and . These particular increments are representable accurately. The example demonstrates a failure mechanism, not a blanket assertion that the recurrence always computes an exact variance.
Worked example 1.1.7
(A reduction plan with explicit resource costs)
Suppose records are partitioned into nonempty blocks, and a machine can store a block of at most records. A one-pass summary needs arithmetic operations overall and state per worker beyond its input buffer. Returning three numbers per worker transfers summary fields, rather than sending all records to the reducer. This count assumes the records have already been placed at workers; reading and distributing input still cost time.
A serial reducer takes merges and has a chain of that length. A balanced binary tree still takes merges in total, but its merge depth is if communication and workers permit parallel execution. For eight blocks there are seven merges and three levels. A shallow tree can reduce the number of dependent rounding stages, but the shape alone is not a proved relative-error bound for every data set. Communication latency, skewed block sizes and scheduling can dominate wall-clock time.
If one worker times out and its block is retried, the reducer must count that block exactly once. The merge formula handles disjoint blocks. Applying it twice to the same block correctly summarizes a duplicated multiset, which is the wrong data set for the original request. An algebraically correct reducer does not supply exactly-once data handling by itself.
A minimal implementation starts from an empty state, initializes from the first accepted finite observation, and uses the update for later records. It should make a deliberate policy for missing values and nonfinite values. Silently skipping missing records changes the target population; silently allowing a nonfinite value can contaminate every later state. Record both the accepted count and, when relevant, a rejected-record count so that the result can be interpreted.
Implementation checks should exercise distinct contracts: a singleton, constant data, unequal block sizes, a large offset, an empty partition and a duplicated partition identifier. Comparing several merge trees is useful for detecting implementation mistakes and measuring numerical sensitivity. Requiring bitwise equality between arbitrary trees would impose a property that ordinary floating-point addition does not possess.
Common mistakes
Common mistake
(Exact invariance is not numerical reproducibility)
Exact summaries depend only on the multiset; finite-precision summaries may also depend on ordering, tree shape, precision and compiler decisions. Reproducible experiments should record these choices where they matter. Changing parallel worker counts can change a reduction tree even when the source data and random seed are fixed.
Common mistake
(A negative computed variance is a diagnostic)
Treating a negative computed variance as evidence of negative variability is wrong. The exact centered sum is nonnegative. A tiny negative value caused by roundoff needs investigation under a documented numerical tolerance; a large negative value points to a bug, overflow or an unstable formula. Blindly replacing every negative result by zero can hide such failures. Likewise, a zero sample variance from one observation is not defined by dividing by .
Common mistake
(A summary does not determine the data)
Counts, means and centered sums cannot reconstruct quantiles, outlier locations or multimodality. For example, and both have count , mean and centered sum , yet the first has two separated clusters and the second has a central pair. Choose the retained state from the actual downstream question, and preserve raw data or richer summaries when that question needs them.
Summary
The triple of count, mean and centered sum is sufficient for exact mean–variance merging. The correction involving the difference of block means accounts for variability between blocks. Centered recurrences avoid one important cancellation mechanism, while finite precision, record validity and duplicate handling remain separate concerns. Resource analysis should distinguish total work, parallel depth, memory, input movement and summary communication; these quantities explain different bottlenecks.
Exercises
Quick check
(Starting with the summary of , append . Compute the mean, centered sum, descriptive variance and sample variance, and check the result by deviations from the final mean.)
Solution · Answer
The initial mean is and centered sum is . The new deviation is and the new mean is . The update gives . The descriptive variance is , and the sample variance is . Directly, the final deviations are , whose squared sum is . Both checks use the final mean, not the old one.
Quick check
(Block contains four copies of and block contains two copies of , so each block variance is zero. Find the combined mean and descriptive variance, and explain why averaging the block variances fails.)
Solution · Answer
The mean is . The difference between block means is , so and . Directly, four squared deviations equal and two equal , giving . The within-block spreads vanish, but the blocks are separated; averaging their zero variances discards all that separation.
Quick check
(Prove that shifting every observation by a constant leaves unchanged and shifts the mean by . Then explain why adding an extremely large offset can still change the computed floating-point variance.)
Solution · Answer
The shifted mean is . Therefore each shifted deviation is , proving exact invariance of . In floating point, converting to a stored number may merge distinct values when the spacing between representable numbers exceeds their separation. Later subtraction cannot undo that input rounding. In addition, different rounded arithmetic paths can perturb the recurrence even if the distinct inputs remain representable.
Quick check
(There are sixteen nonempty partitions. Compare a serial and a balanced reduction in total merges and dependency depth. A retry accidentally adds partition 5 twice. Does a deterministic tree repair the statistical error? Describe one required data-handling invariant.)
Solution · Answer
Both schemes use fifteen merges. The serial chain has depth fifteen; a balanced tree has depth four. Counting partition 5 twice changes the multiset and usually changes its statistics. A deterministic tree makes that incorrect computation repeatable but cannot identify or remove the duplicate. One suitable invariant is that every expected partition identifier contributes exactly one accepted summary for one fixed input version. A reducer can check identifiers and counts before applying the numerical merge; the mathematical recurrence assumes this disjointness contract.