Concept

Concentration inequality

A bound on how much probability can sit far from a distribution's average. What separates one from another is how much it assumes — a variance, a bounded range, an exponential moment — and correspondingly how fast the bound falls away.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as tail bound — the same set of essays touches all of them, so they are one junction rather than several.

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

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

Named alongside it

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

Heavy tails Tail bound Central limit theorem Convergence rate Expectation Extremal example Large deviations Legendre transform Moment generating function Normal distribution Random walk Rate function

All concepts