How far from the average a thing can be

A quantity has an average. It also has a spread, measured the standard way: take the squared distance of each outcome from the average, weight each by how likely it is, add them up, and take the square root. Those two numbers are the whole of what is assumed here. Nothing about the shape of the distribution, nothing about how many outcomes there are, nothing about whether it is symmetric.

From those two numbers alone, the chance of landing far out is bounded.

The bound is one over the square of the window width: beyond two standard deviations, at most a quarter of the probability; beyond three, at most a ninth; beyond ten, at most a hundredth. It is due to Chebyshev, it is proved in three lines, and it holds for every distribution that has a variance at all.

Three lines #

The variance is an average of squared distances. Some of those squared distances are large and some are small, and the whole argument is that the large ones cannot be too common or they would make the average bigger than it is.

Write σ for the standard deviation and consider the outcomes at distance kσ or more from the mean. Each of those contributes at least (kσ)² to the average of squared distances, weighted by its probability. So if the total probability of that region is P, the variance is at least P × k²σ².

But the variance is σ². So σ² ≥ P k²σ², and dividing through gives P ≤ 1/k².

That is the whole proof. It throws away the contribution of everything inside the window — treating it as zero, which is generous — and it treats every outcome outside the window as if it sat exactly on the boundary, which is also generous. Two crude approximations, and out comes a bound that cannot be improved.

Why it cannot be improved #

A bound that is true is one thing; a bound that is attained is another, and the difference decides whether the inequality is a tool or a curiosity.

Both approximations in the proof become equalities for the same distribution. Put all the inside probability at exactly the mean, so its contribution to the variance really is zero, and put all the outside probability at exactly k standard deviations out, so each contributes exactly (kσ)². Then the two inequalities in the proof are equalities, and the mass outside is exactly 1/k².

Such a distribution exists for every k above one: it takes the value −k with probability 1/(2k²), the value +k with the same probability, and 0 the rest of the time. Its variance works out to 1 exactly, and the figure computes both the variance and the tail mass from the three weights rather than quoting them.

So the inequality is sharp. Any bound better than 1/k² would be false for that distribution, and it follows that no argument using only a mean and a variance can do better — the improvement would have to assume something more.

How far from sharp it usually is #

Sharp in general does not mean sharp in any particular case, and for the distributions anybody actually meets the bound is wildly loose.

For a normal distribution the probability beyond three standard deviations is about 0.0027, against a bound of one ninth — forty times too generous. For a coin flip taking two values it is even further out. The staircases in the figure are the honest answer for each distribution, and the bound sits well above all of them.

This gap is the price of the hypothesis being so weak. The bound has to cover the three-point distribution, which is as bad as a distribution with that variance can be, so it must be loose for everything better behaved. Assuming more — that the distribution is a sum of many independent pieces, say, or that its tails decay exponentially — buys much sharper bounds, and the whole subject of concentration inequalities is a catalogue of what each extra assumption buys.

What it is for #

Three uses, and none of them involves knowing the distribution.

Guaranteeing a simulation. Estimating π by dropping needles produces an answer whose error can be bounded by this inequality and by nothing weaker, because the estimator’s distribution is not known in closed form. The variance is computable, the bound applies, and the number of trials needed for a stated confidence follows.

Proving a limit theorem. The weak law of large numbers — that the average of many independent copies settles on the mean — follows in one line: the variance of the average of n copies is σ²/n, so the chance of the average being more than ε from the mean is at most σ²/(nε²), which goes to zero. That is the shortest complete proof of a genuine theorem anywhere in probability, and it uses this inequality as its only ingredient.

Bounding what cannot be computed. In the analysis of an algorithm whose running time depends on random choices, or of a physical measurement whose error distribution is unknown, the variance is often computable when the distribution is not. Chebyshev converts a variance into a statement about how often things go badly wrong, and it is frequently the only such statement available.

The distance a random walk gets to #

The clearest place to watch the bound do useful work is a quantity whose distribution is awkward and whose variance is trivial.

A walk of n steps, each one place left or right with equal chance, ends at a position whose average is zero and whose variance is exactly n — because the steps are independent, so the variances add, and each step has variance 1. So the standard deviation is √n, and Chebyshev says at once that the walk is beyond k√n with probability at most 1/k².

That is a complete answer to how far does a random walk get without any of the combinatorics. The exact distribution of the endpoint is a binomial coefficient divided by a power of two, which is a perfectly good formula and an awkward one to reason with; the bound needs two facts and a division.

The walk that comes home is a different question about the same object, and it is worth noting how differently the two are answered. Whether a walk returns to the origin infinitely often is settled by summing a series and depends delicately on the dimension. How far it typically gets is settled by adding variances, and works in any dimension without change.

Averaging is what makes the bound bite #

The variance of an average of n independent copies is σ²/n, so its standard deviation is σ/√n. Feeding that into the inequality gives the statement that makes the whole of statistics possible: the average of n copies is within kσ/√n of the true mean with probability at least 1 − 1/k².

Every number in that sentence is computable from one variance and one sample size, and none of it needs the shape of the distribution. The band drawn in the figure above is exactly that, and the seven runs stay inside it not because they were selected but because the arithmetic says most runs will.

The 1/√n is the rate, and it is a harsh one. Cutting the error in half needs four times the work; adding a decimal place needs a hundred times. It is the same rate that makes Monte Carlo estimation slow and the same rate that the needle experiment is limited by, and no amount of cleverness about the sampling changes the exponent — only the constant in front of it.

Where the hypothesis fails #

The inequality assumes a variance exists, and some distributions have none.

The Cauchy distribution — the ratio of two independent normal quantities, or equivalently the tangent of a uniformly random angle — has tails heavy enough that the average of the squared distances diverges. It has no variance, and so no version of this bound applies. Worse, it has no mean either: the average of many independent copies does not settle down at all, but has the same distribution as a single copy however many are taken.

That is not an exotic corner. Ratios turn up constantly, and a quantity built as a ratio should be treated as suspect until its tails have been looked at. The same warning applies to the central limit theorem, which also needs a finite variance and which also fails without one — and fails silently, in the sense that a simulation of a heavy-tailed quantity produces perfectly plausible-looking histograms that are converging to nothing.

The one-sided version is worth knowing too. Chebyshev’s inequality is symmetric and most quantities are not, and Cantelli’s one-sided version replaces 1/k² with 1/(1 + k²) for the probability of exceeding the mean by kσ in one direction — a better bound, from the same information, obtained by a slightly cleverer choice in the proof.

The shape the bound refuses to use #

Set the inequality beside the central limit theorem and the trade becomes explicit. The limit theorem says that a sum of many independent pieces has an approximately bell-shaped distribution, from which the chance of being three standard deviations out is about 0.0027. The inequality says nothing about the shape and gets 0.111 instead.

Forty times worse — and it applies to a single roll of a die, to a quantity built from ten pieces rather than ten thousand, to a distribution nobody has characterised, and to a quantity whose independence is doubtful. The limit theorem’s answer is far better and rests on hypotheses that have to be argued for each time. That is the whole relationship between the two, and it is why both are taught.

There is also a case where the comparison inverts. For a sum of a few heavy-tailed pieces the bell approximation is simply wrong at three standard deviations — the true tail is far heavier than 0.0027 — while Chebyshev’s bound remains true, because it was never approximating anything. A bound that is always right and usually loose is a different kind of object from an approximation that is usually excellent and sometimes badly wrong, and a reader who has only met the second is liable to trust it in the places it fails.

What it costs #

Almost nothing, and that is the point.

Applying the inequality costs one variance computation. The variance of a sum of independent quantities is the sum of the variances, so for an average of n copies it is arithmetic; there is no integration, no distribution to characterise, no simulation.

The figures compute their tail masses by summing over the outcomes exactly rather than by sampling, which is possible because the distributions drawn are finite. That distinction matters for what the pictures are evidence of: a sampled tail mass would be an estimate with its own error, and the claim being checked here is an inequality between two exact numbers.

The one figure on this page that does sample is the needle-dropping one, and it is sampling because the subject of that figure is an estimate.

What the picture cannot show #

The bound is a statement about every distribution with a finite variance, and every figure here draws a handful of them. A sweep across four distributions is evidence about four distributions; the proof is what covers the rest, and the proof is three lines of algebra that no picture contains.

Nor can a figure of a discrete distribution show what goes wrong for a continuous one with heavy tails. The bars can be made shorter and more numerous, and the divergence that kills the Cauchy case happens out where no drawing extends.

And the extremal distribution is drawn at one value of k. There is a different extremal distribution for every k, and no single distribution meets the bound at more than one window width — which is worth stating because it means the bound is sharp pointwise and not uniformly. There is no distribution for which Chebyshev is tight everywhere.

The ladder from here #

Rungs above: Markov’s inequality, which is the same argument one step earlier and from which Chebyshev follows by applying it to the squared deviation. Cantelli’s one-sided bound. Chernoff bounds, where assuming the quantity is a sum of independent bounded pieces buys an exponentially small tail instead of a polynomial one. Hoeffding’s inequality and the concentration of measure phenomenon, where high dimension makes almost every function nearly constant. The Berry–Esseen theorem, which says how fast the bell curve approximation arrives. Martingale concentration, where the independence assumption is weakened to something a process can satisfy. And the median-of-means trick, which converts a bound with a weak tail into one with a strong tail by running the estimate several times.

The shape of the idea #

The argument on this page is an instance of a manoeuvre that appears whenever an average is used to bound a part: if a few outcomes were much larger than the average allows, they would drag the average up, so there cannot be many of them.

That is the pigeonhole principle with weights attached. Pigeonhole says that if n + 1 things go into n boxes some box has two; the averaging version says that if the mean of a collection is m, something in it is at least m. Chebyshev is the same observation applied to squared distances, and the sharpness comes from the fact that the observation is exactly right when everything sits at one of two extremes.

What makes it worth its own essay rather than a remark is the second figure. A bound proved by throwing away two whole terms ought to be badly loose, and it is — for every distribution except the one it was, in effect, designed for. Finding that distribution is what turns an inequality from a true statement into a complete answer.