Heavy tails
Named by 14 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
ExpectationVarianceNormal distributionIndependenceMedianRandom walkTail boundBinomial distributionCentral limit theoremConcentration inequalityConvergenceConvergence rate