Concentration — the series
-
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 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 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.
-
A sphere that is nearly all equator
On an ordinary globe, the band within a tenth of the radius of the equator holds a tenth of the surface. On a sphere in a thousand dimensions the same band holds 99.85% of it, and the band of a fifth holds all but about two parts in ten billion. Almost every point of a high-dimensional sphere is near every equator at once — and so any function that cannot change quickly is, over almost all of the sphere, almost constant.
-
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.