Concept

Heavy tails

A distribution whose extreme values are common enough to dominate averages, and whose variance or mean may not exist at all. The largest of a sample is then comparable to the whole sum, which is why averaging such quantities buys so little.

Named by 14 essays across 3 fields — each of them below, with the objects they name alongside it.

A Galton board after 600 balls. 600 balls fall through 12 rows of pegs, each bouncing left or right at random, and pile up in a bell-shaped heap.

A bell curve assembled out of coin flips

Drop six hundred balls through a board of pegs, each bouncing left or right at random, and they pile up in a shape that can be predicted precisely. Nothing coordinated them.

probability · Central limit
five values, unevenly weighted, and the mass outside 3 standard deviations. A distribution drawn as bars, with the windows one and a half, two and three standard deviations wide marked. The probability outside each window is summed and compared with the bound that knows only the variance.

How far from the average a thing can be

Knowing only an average and a spread — nothing about the shape, nothing about the number of outcomes, nothing about symmetry — the chance of landing three standard deviations out is at most one in nine. And there is a distribution that lands there exactly that often, so the bound cannot be improved.

probability · Concentration
Averages of a heavy-tailed quantity, which never settle. Running averages of draws from a Cauchy distribution, which jump rather than converge, beside the cumulative distributions of averages of 1, 4 and 16 draws, which lie on top of one another.

An average that never settles

The average of many independent quantities is supposed to steady as their number grows. For one famous distribution it does not steady at all — the average of a thousand draws has exactly the same distribution as a single draw, and no amount of further averaging changes it.

probability · Central limit
How fast a sum becomes a bell curve. The largest gap between the distribution of a standardised sum and the bell curve, against the number of terms, on logarithmic axes. Both summands fall along a line of slope about minus a half.

How fast the bell arrives

The limit theorem says a standardised sum approaches the bell curve and says nothing about when. The rate is one over the square root of the number of terms, the constant in front is made of the third moment, and both are visible.

probability · Central limit
The chance the average clears 0.75, against the number of draws. The exact probability that the average of n draws exceeds a fixed level, on a logarithmic scale, falling along a straight line whose slope is the rate function, with the normal approximation drawn beside it and diverging.

The tail is not a bell

The limit theorem describes a window of width one over the root of n around the mean; ask instead for the chance that an average lands a fixed distance away and the answer falls exponentially, at a rate computed from the summand before any n is chosen.

probability · Central limit
How far each estimate can stray, when rare jumps are possible. The error that the sample mean and the median of 12 block means stay within, at confidence levels from 80% to 99.9%, over 60000 repeated samples of 120 draws from normal draws with rare large jumps, with Chebyshev's guarantee for the mean.

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.

probability · Concentration
What a rule collects when every value comes from the same distribution. uniform on [0, 1]: best rule 0.995, one threshold 0.635 of E[max] at n = 200; exponential: best rule 0.905, one threshold 0.678 of E[max] at n = 200; Pareto, tail exponent 2: best rule 0.802, one threshold 0.714 of E[max] at n = 200; Pareto, tail exponent 1.2: best rule 0.802, one threshold 0.682 of E[max] at n = 200.

When every value comes from the same hat

A rule that sees values one at a time and must keep or discard each on the spot can guarantee half of what a prophet collects, and no more, when the values come from different distributions. When they all come from the same one, the guarantee rises to 0.745 — and a single fixed threshold, set so that each value crosses it with chance 1/n, already secures 1 − 1/e. For bounded values the best rule collects nearly everything; only a heavy tail, where one enormous value carries the prize, keeps the gap open.

probability · Optimal stopping
A random sequence that shrinks, grows or wanders, by one parameter. Runs of tₖ₊₁ = tₖ ± β·tₖ₋₁ at β = 0.6, 0.70258, 0.8 on a logarithmic scale: shrinking, wandering and growing.

A threshold no average can see

Damp the random Fibonacci sequence — add or subtract β times the term before last, by a coin — and somewhere between β = 0.6 and β = 0.8 almost every run stops shrinking and starts growing. The switch is at β ≈ 0.70258. The average of the squares, which can be computed exactly, grows for every β there is, so the one number that decides the sequence's fate is invisible to the one number anybody can compute.

dynamics · Sensitive dependence
One shared birthday, as a measurement of the year. Histogram over 20000 rooms of the estimate T(T − 1)/2 from the first shared birthday, averaging 361 against 365, spread widely.

Counting a population by its repeats

The birthday problem runs forwards from a known year to the chance of a match. Run it backwards and the matches measure the year: count how many pairs among the draws came out the same, and the number of kinds is about the number of pairs divided by that. It costs the square root of the population rather than a census of it — and when the kinds are unevenly common, what the repeats measure is not how many kinds there are but how many they behave like.

probability · Birthday problem
Newton's method for z² − 1: two half-planes and the line between. The complex plane split down the imaginary axis into two shaded halves, the roots ±1 marked, and five orbits of Newton's method each converging to the root on its own side.

Chaos on the line between two roots

Newton's method for a quadratic is the one case solved completely: every starting point goes to the nearer root, and the plane splits into two half-planes. Cayley did it in 1879. What his solution also contains is a line on which the method never settles — and a change of variable shows that on that line Newton's method is exactly the doubling map, the simplest chaos there is. Run on the real line for x² + 1, which has no real root to find, it becomes a source of Cauchy-distributed randomness.

dynamics · Newton basins
Records in a thousand draws, and the lengthening waits between them. A sequence of 1000 uniform draws on a logarithmic position axis, with records at positions 1, 6, 11, 27, 36, 145, 539, 927.

A wait that ends and has no average

Draw a number, then keep drawing until one beats it. Half the time the very next draw does. The wait is certain to end, it is usually short, and its average is infinite — and the chance of still waiting after n draws is exactly 1/(n + 1), whatever the numbers are drawn from, because symmetry is the only thing the calculation uses.

probability · Expectation
A random walk winding round a puncture. Lattice walk of 4000 steps around (½, ½); final winding -4.861 turns; box -12..26 × -29..22.

How a random path winds round a point

A path in the plane with one point removed has a class in the punctured plane's fundamental group: how many times it has wound round the point. For a random path the class grows like the logarithm of time, and its spread has a law. Brownian motion follows Spitzer's Cauchy law, so heavy-tailed that the mean winding does not exist; a walk on a grid follows the hyperbolic secant law instead, with tails that fall exponentially. The difference is made entirely by close passes, which a grid forbids. With two points removed the class becomes a word, and some loops wind round neither point and still cannot be shrunk.

topology · Homotopy
The median has a bell of its own. normal: median sd 0.1238 (pred 0.1247), mean spread 0.0985; laplace: median sd 0.1071 (pred 0.0995), mean spread 0.1405; cauchy: median sd 0.1588 (pred 0.1563), mean spread 1.5006

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.

probability · Central limit
How well a trimmed mean estimates the centre, shape by shape. Efficiency of the alpha-trimmed mean for normal: mean 1.000, 10% 0.943, 25% 0.837, median 0.637; logistic: mean 0.912, 10% 0.994, 25% 0.950, median 0.750; contam: mean 0.698, 10% 0.969, 25% 0.901, median 0.697; t5: mean 0.800, 10% 0.989, 25% 0.966, median 0.769; laplace: mean 0.500, 10% 0.669, 25% 0.815, median 1.000; t3: mean 0.500, 10% 0.932, 25% 0.984, median 0.811; cauchy: mean 0.000, 10% 0.419, 25% 0.785, median 0.811.

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.

probability · Central limit

Named alongside it

The objects these essays reach for when they reach for this one.

ExpectationVarianceNormal distributionIndependenceMedianRandom walkTail boundBinomial distributionCentral limit theoremConcentration inequalityConvergenceConvergence rate

All concepts