Median
Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.
The median of many small averages
Knowing only that a quantity has a finite spread, the plain average of n samples can be promised to within σ/√(nδ) with confidence 1 − δ, and no better — Chebyshev's bound is tight, and rare large jumps achieve it. Cut the same samples into a dozen blocks, average each block, and take the median of the averages, and the promise improves to within about σ√(log(1/δ)/n). Nothing about the data has been assumed beyond the spread; only the way of combining it has changed.
The matching in the middle
List every stable matching of a market, give each member their stable partners sorted from best to worst, and hand each the one in the middle. Nothing says the result should even be a matching — two people might pick the same partner — and yet it always is one, it is always stable, and the other side gets its median partners too.
The best average is the worst bet
A coin lands heads six times in ten and pays even money. Stake everything on every toss and the expected wealth grows by a fifth a toss — and the bettor is ruined at the first tail, which is certain to come. Stake a fifth of wealth each time instead and the average grows far more slowly, while the typical bettor grows faster than with any other fraction. The expectation is maximised by the strategy almost nobody should use.
The middle value has a bell of its own
The central limit theorem is a theorem about sums, and the median of a sample is not a sum of anything. It has a bell all the same: the middle of n draws spreads like 1/(2f√n), where f is the height of the density at the middle — not the variance, which the median never consults. That one number decides when the median beats the average, by a factor of two for a two-sided exponential and outright for the Cauchy law; and where the density is nought at the middle, the bell fails, slowing to a fourth root or splitting in two.
Sellers in a square town
On a street, two sellers settle back to back in the middle, three never settle, and four settle in pairs at the quarter points. Spread the customers over a square town instead and the first fact survives while the third does not: the street's pairs leave a seller half a per cent of the town to gain by stepping off the line. Computing every seller's market exactly and searching for an arrangement where nobody wants to move finds one only for two sellers.
The best middle when the shape is unknown
The mean is the best estimate of a centre when the data are normal and worthless when they are Cauchy. The median is best for Laplace data and wastes a third of normal data. Between them lie the trimmed means — drop a share from each end, average the rest — and across seven symmetric shapes the best guarantee comes from trimming about 28 per cent from each end, which never does worse than 81 per cent of the best possible. Peter Bickel proved in 1965 that trimming can never cost more than a known factor against the mean, whatever the shape.
Named alongside it
The objects these essays reach for when they reach for this one.
Heavy tailsEstimatorVarianceBest responseBinomial distributionBlocking pairCentral limit theoremChebyshev inequalityConfidenceEfficiencyEntropyExhaustive search