Concentration inequality
Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
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 bound is the answer to a search
Chebyshev's inequality is not a clever estimate that happens to be sharp. It is the exact answer to a maximisation over all distributions with a stated mean and variance, and the polynomial that proves nothing beats it is the certificate a search of that kind always produces.
No single input can move it far
Independence was never the hypothesis doing the work. A quantity built from many separately drawn inputs concentrates whenever changing one of them moves it only a little — and that covers quantities which are not sums of anything and have no formula at all.
The ball that is largest in five dimensions
A disc of radius one has area π, a ball of radius one volume 4π/3, and in each further dimension the unit ball grows — until five, where its volume is 5.264, after which it shrinks towards nothing. The recursion that shows it is the ring dissection of the disc, done one dimension at a time, and the shrinking is not the ball getting small: it is almost all of a high-dimensional cube lying outside the ball, and almost all of the ball lying in a thin rind at its surface.
Drawn without putting back
Every concentration bound on this shelf assumes the draws are independent. A real sample is not: a pollster does not ring the same person twice, and every ball taken from an urn changes what is left in it. The dependence runs the helpful way. Wassily Hoeffding proved in 1963 that a sample drawn without replacement is at least as concentrated as one drawn with it, for every convex measure of spread at once — and the variance falls by an exact factor that reaches zero when the whole urn is taken.
Charged for the variance, not the range
Hoeffding's inequality knows one thing about each term of a sum: the interval it lies in. For ten thousand coins that each land heads once in a thousand, that makes it promise almost nothing — a 92% chance of thirty heads, when the truth is two in ten million. Tell the bound each term's variance as well and it changes character: Bernstein's and Bennett's inequalities decay like the normal curve while the deviation is small and like a Poisson tail beyond, and for rare events they are millions of times sharper.
Named alongside it
The objects these essays reach for when they reach for this one.
Tail boundVarianceExpectationExtremal exampleMoment generating functionConvergence rateExhaustive searchHeavy tailsHoeffding inequalityNormal distributionRandom walkBinomial distribution