The middle value has a bell of its own

Every essay on this shelf so far has been about sums. The average settles and the wobble does not divided a sum by $n$ and watched it collapse to a point, then divided by $\sqrt n$ and watched a bell appear. The shape that averaging leaves alone explained why the bell is the shape that adding returns unchanged. How fast the bell arrives priced the approach to it in third moments, and a share that depends on the average found sums of logarithms deciding even a question about leading digits. Every one of those arguments starts by writing the quantity of interest as $X_1 + X_2 + \dots + X_n$, and every one of them needs that sum.

The sample median is not a sum. Sort $n$ draws and take the one in the middle; nothing has been added, and a change to the largest draw, however large, leaves the answer alone. An average that never settles used exactly that to rescue the Cauchy distribution, whose averages never steady: the median of Cauchy draws, it noted in passing, settles at the ordinary rate. This essay is about why — what law the median obeys, what sets its width, and where that law breaks.

The answer is a central limit theorem of its own, older than most of the ones on this shelf: Laplace had it by 1818, when he compared the middle observation with least squares as ways of fixing a quantity from measurements. The median of $n$ draws is close to normal, centred on the distribution’s median $m$, with standard deviation

$$\frac{1}{2 f(m) \sqrt n},$$

where $f(m)$ is the height of the density at the middle. The variance appears nowhere. The tails appear nowhere. The whole width of the bell is set by how thickly the data lie at one point.

The three panels above say most of what follows. On normal data the means are the narrower histogram, as the textbook bell promises. On Laplace data — a two-sided exponential, with a sharp peak at the middle and tails that fall off more slowly than the normal’s — the medians are narrower. On Cauchy data the means do not form a histogram worth the name, and the medians form exactly the bell their formula draws. One rule fits all three medians, and it uses nothing but the height of each density at nought.

Reading the coin flips sideways #

The proof is short enough to carry around, and it turns the median back into a sum after all — just not a sum of the draws.

Fix a number $t$ and ask for the chance that the median of $n$ draws is at most $t$. Take $n$ odd, $n = 2k + 1$, so that the median is the $(k+1)$-th smallest draw. That draw is at most $t$ exactly when at least $k + 1$ of the draws are at most $t$. Each draw lands at or below $t$ with probability $F(t)$, the distribution function, independently of the others. So the number of draws at or below $t$ is a binomial count, a sum of $n$ coin flips each landing heads with probability $F(t)$, and

$$P(\text{median} \le t) = P\big(\text{Bin}(n, F(t)) \ge k + 1\big).$$

That is an identity, not an approximation, and it hands the median to the oldest limit theorem there is. A binomial count with $n$ trials and success chance $p$ has mean $np$ and spread $\sqrt{np(1-p)}$, and it is close to normal. Near the middle, $F(t) \approx \tfrac12 + f(m)(t - m)$: moving $t$ a little past the median raises the success chance by the density times the distance. So the count’s mean moves by $n f(m)(t - m)$, while its spread stays about $\sqrt n / 2$. The median crosses $t$ when the count crosses $n/2$, which happens when the shift in the mean is comparable to the spread — when $t - m$ is comparable to $1/(2 f(m) \sqrt n)$.

The two curves in the top panel cannot be told apart, and the strip below shows how close they are: the exact law and the bell differ by at most $0.0006$ anywhere, at only 101 draws. The difference has a shape, a small wave that runs negative to the left of the middle and positive to the right, which says the exact law of the median is slightly more concentrated than its bell. That is the beginning of a correction series of the kind the Berry–Esseen story tells for sums, and for a smooth density it is of order $1/n$ rather than $1/\sqrt n$, because the curvature of $F$ at a symmetric middle vanishes.

The argument explains the formula’s most surprising feature. The median’s spread involves the density at one point because only the behaviour of $F$ near $m$ ever enters: a draw far out in the tail counts as one draw below $t$ or one draw above it, whatever its size. The tail can be as heavy as the Cauchy law’s and the count does not notice. An average that never settles called this the property that no single term can move the median more than one position; the binomial identity is that property turned into a distribution.

The same identity exposes the hypothesis the theorem needs, which is easy to miss. The approximation $F(t) \approx \tfrac12 + f(m)(t - m)$ requires $F$ to have a slope at the middle, and the slope to be positive. If the density is zero at $m$, the count barely moves as $t$ moves, and the whole calculation changes scale. If the density has a corner at $m$ — positive, but with different slopes on the two sides — the linear approximation holds but its error is larger than for a smooth density, and the bell arrives more slowly. All three cases turn up below.

Which middle is better #

Two estimates of the same centre, from the same sample, now have two bells. For symmetric data both are centred on the same point, and both have spreads proportional to $1/\sqrt n$, so they can be compared by the constants alone. The mean’s spread is $\sigma/\sqrt n$; the median’s is $1/(2 f(m) \sqrt n)$. The ratio of their variances, the mean’s over the median’s, is

$$4 f(m)^2 \sigma^2,$$

and it does not depend on $n$ at all. Above one the median is the better estimate; below one the mean is. Statisticians call this the asymptotic relative efficiency, and its value is a single dimensionless number for each shape of distribution — rescaling the data multiplies $\sigma$ by a factor and divides $f(m)$ by the same factor, and the product is untouched.

For normal data the ratio is $4 \cdot \tfrac{1}{2\pi} \cdot 1 = 2/\pi \approx 0.637$, the figure every statistics course quotes: the median wastes about 36 per cent of the sample, in the sense that a mean from 637 draws is as precise as a median from a thousand. For uniform data it is a third — the uniform density is flat, so it gives the median no extra crowding at the middle, while its bounded range makes the mean unusually good. For the logistic distribution, a bell with slightly heavier tails than the normal, it is $\pi^2/12 \approx 0.822$. For Laplace data it is exactly two: the median is twice as efficient. For Student’s $t$ with three degrees of freedom, whose variance is finite but whose tails fall only like the fourth power, it is $16/\pi^2 \approx 1.62$.

The pattern is the one the formula predicts. The ratio compares a peak with a spread, so it grows when the distribution puts a sharp concentration at its middle and leaves weight far out in its tails. The uniform distribution is the extreme in one direction, and there is a theorem to match: among symmetric distributions whose density falls away from the middle, a third is the worst the median can do, and the uniform attains it. In the other direction there is no limit, because $\sigma$ can be made as large as desired without lowering the peak. At the Cauchy end $\sigma$ is infinite, the ratio is infinite, and the comparison stops being a comparison: the mean is not merely worse, it does not converge.

The Laplace distribution is the case where the median is not just better than the mean but the best estimate there is. Its density is proportional to $e^{-|x - m|}$, so the likelihood of a sample is largest where $\sum |x_i - m|$ is smallest, and the sum of absolute distances is minimised at the median. In the same way the normal likelihood is largest where $\sum (x_i - m)^2$ is smallest, which is at the mean. Each estimator is the maximum-likelihood estimate for the shape whose logarithm is its loss, and each is the most precise estimate available for that shape — which is why the normal ratio and the Laplace ratio sit on opposite sides of one.

The bracketed numbers in the figure are worth reading against the theory. Four of the five agree within a few per cent. The Laplace bar does not: at 101 draws the measured ratio is 1.72, not 2. Nothing is wrong with the theorem; the Laplace density has a corner at its peak, the linear approximation to $F$ near the middle is good only to first order, and the error it leaves shrinks like $1/\sqrt n$ rather than $1/n$. At 101 draws the Laplace median’s spread is about 8 per cent wider than its formula; at 1,001 draws, about 2 per cent. The asymptotic ratio is a statement about the limit, and a sharp peak is exactly the feature that makes the limit slow.

No data at the middle #

The theorem divides by $f(m)$, and the most instructive thing to do with a formula that divides by something is to set that something to nought.

Take a density shaped like a letter V: $|x|$ on the interval $[-1, 1]$, heaviest at the ends and empty at the centre. Its median is nought, and its density there is nought. Rerun the coin-flip argument. Moving $t$ a little past the middle raises the chance that a draw falls below $t$ not by $f(m)\,t$, which is nothing, but by the area of a thin triangle, $t^2/2$. The count of draws below $t$ moves by $n t^2/2$, its spread is still $\sqrt n/2$, and the median crosses $t$ when $n t^2$ is comparable to $\sqrt n$ — when $t$ is comparable to $n^{-1/4}$.

The two lines in the figure are the two rates. The normal medians shrink by a factor of ten for every hundredfold increase in the sample, the square-root rule. The V-shaped medians shrink by a factor of ten only for every ten-thousandfold increase — a fourth-root rule, measured at a slope of $-0.248$. At 3,001 draws the normal median is known to about $0.023$ and the V-shaped median only to about $0.12$, although both distributions have comparable spreads and both are perfectly symmetric about nought.

The law is not a bell either. The same calculation says that the chance the rescaled median $n^{1/4} \cdot \text{median}$ is at most $s$ tends to $\Phi(\operatorname{sign}(s)\, s^2)$, where $\Phi$ is the normal distribution function. Its density is $2|s|\,\varphi(s^2)$, which is nought at $s = 0$: the median of V-shaped data has two humps, one on each side of the middle, and is least likely to be found exactly where the true median is. That is intuitive once said. There are no draws near nought, so the middle draw of the sample is almost never near nought; it is the innermost draw on whichever side happens to hold the majority.

The general rule follows the same arithmetic. A density that vanishes at the middle like $|x|^a$ makes $F(t) - \tfrac12$ grow like $|t|^{a+1}$, and the median spreads like $n^{-1/(2(a+1))}$. The exponent $a = 0$ is the ordinary case and gives the square root; $a = 1$ is the V; a density that is flat to high order at the middle gives a median that barely improves with data at all. The rate at which a sample pins down its middle is the rate at which the data crowd the middle, and nothing about the rest of the distribution can compensate.

A gap at the middle #

Push the V further. Take a distribution with half its weight spread evenly on $[-2, -1]$ and half on $[1, 2]$, and nothing between. Every point of $[-1, 1]$ now has half the weight on each side of it, so every one of them is a median of the distribution; the theorem’s $m$ is not even defined.

The means do not care. The distribution has a perfectly good mean, nought, and a finite variance, $7/3$, and the means of 101 draws form the bell the ordinary theorem promises, with spread $\sqrt{7/3}/\sqrt{101} \approx 0.152$. The medians never land in the gap at all, because the middle draw of a sample is a draw, and there are no draws in the gap. They fall into two clumps, one just left of $-1$ and one just right of $+1$, and the clumps are equally full — in the run behind the figure, 49.5 per cent on the left. The sample’s median is whichever edge of the gap the majority of the sample happens to sit beyond, and the count that decides it is a fair coin tossed 101 times.

No rescaling turns this into a bell. Multiplying by $\sqrt n$ or any power of $n$ pushes the two clumps further apart; the median does not converge to anything, in any sense, because there is nothing for it to converge to. A sample of a million draws has a median within a hair of $-1$ or of $+1$, and which one is a coin flip. Here the median is the worse estimate of the centre by any measure — it is never within a distance of one of the true centre — and the average, which ignores the gap, is the better one.

This is the honest limit of the argument in an average that never settles. There the median’s virtue was that it ignores how far the extremes lie; here the same virtue is the fault, because the median reads only the local crowding at the middle and the middle is empty. The two failures are mirror images. The mean fails when the tails are too heavy for the variance to exist, and the median fails when the centre is too thin for the density to be positive. A robust estimate of the centre — the median of many small averages is one — is a compromise that survives a little of both.

Every quantile has a bell #

Nothing in the coin-flip argument used the number one half except in naming the middle. Replace the median by the $p$-th quantile of the sample, the value with a share $p$ of the draws below it, and the same identity holds with the count compared against $pn$ instead of $n/2$. The binomial now has success chance near $p$, so its spread is $\sqrt{p(1-p)n}$, and the quantile’s spread becomes

$$\frac{\sqrt{p(1-p)}}{f(q_p)\sqrt n},$$

where $q_p$ is the true quantile and $f(q_p)$ the density there. At $p = \tfrac12$ the square root is $\tfrac12$ and the median’s formula comes back.

For normal data the curve in the figure has its floor at the median and climbs steeply towards both ends. Two things push in opposite directions. The factor $\sqrt{p(1-p)}$ is largest at one half, because a coin is most uncertain when it is fair. The density $f(q_p)$ is also largest at the middle, and for the normal it falls so fast in the tails that it wins: the 2nd percentile of 201 draws is known only to a spread of about $0.19$, more than twice the median’s $0.088$. The measured points follow the curve across the middle and drift slightly from it at the extremes, where the quantile is decided by the handful of draws in the tail and the normal approximation to a count of four or five successes is poor.

The picture turns the tail into a question about counting, which is the subject of the tail is not a bell: a quantile far out in a light tail is set by very few draws, its law is skewed, and as $p$ is pushed to the extremes along with $n$ the bell gives way to the extreme-value laws. For estimating a centre, though, the conclusion is the same at every $p$: the precision of a quantile is the density at that quantile, and an estimate built from the middle of the sample inherits the crowding of the data at the middle.

Why the median is the shelf’s odd case #

The central limit theorem for sums depends on three things about the summands — independence, a finite variance and nothing more — and gives a width proportional to the variance. The theorem for the median depends on independence, a positive density at the middle, and nothing more, and gives a width inversely proportional to that density. The two hypotheses are almost disjoint. The Cauchy distribution satisfies the second and not the first. The split distribution satisfies the first and not the second. The normal satisfies both, and there the mean wins; the Laplace satisfies both, and there the median wins.

The deeper reason the median has a bell at all is the one the coin-flip argument made explicit: the median’s distribution function is a binomial tail, and binomial tails are sums. Concentration of this kind does not need its quantity to be a sum, only to be decided by a sum — and the median, which is not changed much by changing one input, is the simplest example of the wider principle in no single input can move it far.

Something practical follows for anyone choosing between the two. The choice is not between a principled estimate and a crude one. It is between two estimates that look at different features of the data — the second moment and the density at the middle — and the better one is whichever feature the data have more of. A sharp, heavy-tailed distribution favours the median; a flat or light-tailed one favours the mean; and a distribution with a hole in the middle punishes the median for reading the one place where nothing is.

Still open: the best middle for an unknown shape #

The comparison above assumes the shape is known. In practice it is not, and the question becomes which single estimate of the centre does best across a whole family of shapes. Trimmed means, which discard a fixed share of the largest and smallest draws and average the rest, interpolate between the mean and the median, and Peter Bickel showed in 1965 that a mean trimmed by a share $\alpha$ at each end is never less efficient than the plain mean by more than a factor $(1 - 2\alpha)^2$, whatever the symmetric shape — while against heavy tails it can be infinitely better. Adaptive estimates that look at the sample to choose how much to trim can be made to match the best estimate for the true shape in the limit, as Charles Stone showed in 1975 for symmetric distributions.

What is not settled is how much of that limit can be had at a sample size anyone uses. The adaptive estimates are proved efficient as $n$ grows without bound, and the Laplace bar in the figure above is a reminder that the limit can be far off at a hundred draws even for an estimate as simple as the median. How large a sample has to be before an adaptive estimate reliably beats a fixed choice, uniformly over reasonable shapes, has no sharp answer, and the computational answer depends on which shapes are counted as reasonable.

A second open edge sits at the middle itself. Every result here took the density at the median as fixed and positive, or as vanishing in a known way. For data whose density near the middle is irregular — oscillating, or vanishing on a set the sample cannot resolve — the rate at which the median settles is governed by the fine structure of $F$ at one point, and describing that rate for general $F$, including how it interacts with the binomial fluctuations that drive the bell, remains a question of local analysis rather than of probability. The median’s bell is a theorem about one point of one function, and most of the open problems about it are problems about how much can be known from that point.