Relative entropy
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
When the whole histogram deviates
A rare average has a price, an exponent that grows with the number of trials. Ask instead for the chance that the whole tally of outcomes comes out wrong, and the exponent is no longer a function of one number — it is a distance between two distributions, and every rare-average rate is a shadow of it.
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 boundCentral limit theoremConcentration inequalityCounting argumentEmpirical distributionEntropyExtremal exampleHoeffding inequalityLarge deviationsMoment generating functionMultinomialPoisson approximation