The bound is the answer to a search

How far from the average a thing can be proves Chebyshev’s inequality in three lines, exhibits a three-point distribution meeting it exactly, and concludes that the bound cannot be improved. Every step of that is correct and it leaves one thing unexplained: why does a proof that throws away two whole terms produce an answer that is exactly right?

The answer is that the bound is not an estimate. It is the value of an optimisation, and the three-line proof is that optimisation’s dual.

The question, stated as a maximisation #

Ask the question the bound answers. Over all distributions with mean $\mu$ and variance $\sigma^2$, what is the largest possible probability of landing at least $k\sigma$ from the mean?

Written out, that is: maximise $\sum_{x \text{ outside}} p_x$ subject to $\sum p_x = 1$, $\sum x\,p_x = \mu$, $\sum x^2 p_x = \mu^2 + \sigma^2$, and $p_x \ge 0$. The objective and every constraint is linear in the probabilities, so this is a linear program — the same kind of object as a linear program in two variables, with one variable per possible value instead of two.

That observation settles several things at once and each is worth taking separately.

The optimum sits on at most three points. A linear program with three equality constraints has an optimal solution with at most three variables non-zero, because a vertex of the feasible region is where enough constraints are tight. So the extremal distribution an earlier essay exhibits is not a lucky find; three constraints force three points, and the figures search only over triples for exactly that reason.

The optimum is attained. The feasible set is closed and bounded, and a linear function on it has a maximum. So the bound is achieved by some distribution and the question of whether it can be improved has a definite answer.

And the answer comes with a proof. That is the part worth the rest of this essay.

What a certificate looks like here #

A linear program’s dual assigns a multiplier to each constraint and asks for the cheapest combination that dominates the objective. Here the constraints are the three moments, so a dual solution is three numbers $a$, $b$, $c$ — and the combination $a + bx + cx^2$ is a polynomial of degree two.

The dual’s feasibility condition is that this polynomial lies above the objective’s coefficient at every value: above $1$ where $x$ is outside the window, and above $0$ everywhere else. Its cost is its average against the stated moments, $a + b\mu + c(\mu^2+\sigma^2)$. And duality says the cheapest such polynomial’s average equals the largest achievable tail mass.

For the two-sided window with mean nought and variance one, the cheapest polynomial is

$$\frac{x^2}{k^2},$$

which is at least one when $|x| \ge k$ and at least nought everywhere, and whose average is $1/k^2$. That is Chebyshev’s inequality, and it is also his proof — the three-line argument is exactly the statement that this polynomial dominates the indicator and that averaging preserves inequalities.

So the proof was never an estimate that happened to be tight. It was a dual solution, the two terms it “threw away” were the slack in the dual constraint at the points the optimum does not use, and the tightness is the complementary slackness that a matched pair of optimal solutions always has.

Reading the tightness off the pair #

Complementary slackness says a primal variable can be positive only where the dual constraint is tight. Here that reads: the extremal distribution puts mass only where the certificate touches the indicator.

The certificate $x^2/k^2$ equals the indicator at exactly three places. At $x = \pm k$ it equals one and the indicator is one. At $x = 0$ it equals nought and the indicator is nought. Everywhere else it is strictly above. So the extremal distribution is supported on $\{-k, 0, k\}$ — which is the distribution that essay exhibits, derived rather than found.

That is worth pausing on because it inverts the usual order of discovery. That essay finds the distribution by asking where the proof’s two inequalities become equalities, which is a good instinct and needs the proof first. The certificate view produces the same answer from the other direction — the support of the optimum is where the dual is tight — and would produce it for any window and any set of moments, without anybody having to guess.

The same program, a different question #

The value of seeing the bound as an optimisation is that changing the question is now a change of objective rather than a new theorem.

Ask for one tail: how much mass can sit above $\mu + k\sigma$? Same constraints, different objective, and the answer is smaller — $1/(1+k^2)$ rather than $1/k^2$. At two deviations that is 0.2 against 0.25; at three, 0.1 against 0.111.

That is Cantelli’s inequality, which how far from the average a thing can be mentions in one sentence as “a better bound, from the same information, obtained by a slightly cleverer choice in the proof”. The cleverer choice is the dual solution, and it is not clever at all once the program is written down: the cheapest quadratic above the one-sided indicator is

$$\left(\frac{x + 1/k}{k + 1/k}\right)^2,$$

which touches the indicator at $x = k$ from above and at $x = -1/k$ from below. Complementary slackness then says the extremal distribution sits on those two points, and it does: mass $1/(1+k^2)$ at $k$ and the rest at $-1/k$.

Two-point and three-point, and why it matters #

The one-sided optimum has two points and the two-sided has three, and the difference is not arbitrary. It is the count of places the certificate touches, and that count is bounded by the certificate’s degree.

A quadratic can touch a two-valued indicator at most twice from above per branch, and the geometry of where the touches can be is what fixes the number. That gives a rule of thumb worth carrying: a bound derived from the first $m$ moments has an extremal distribution on at most $m+1$ points, because the certificate is a polynomial of degree $m$ and the primal has $m+1$ equality constraints.

So a bound from the mean alone — Markov’s inequality — has a two-point extremal distribution, and it does: all the mass at nought except a sliver at the threshold. A bound from four moments has a five-point one. The whole family is one program with a different degree, and the answers get better as the degree rises because a higher-degree certificate can hug the indicator more closely.

That is the exchange rate that essay describes as “the exchange rate between hypotheses and tightness”, made exact: each extra moment is one more constraint in the primal and one more degree in the certificate.

Markov’s inequality, which is the same program with one constraint fewer #

The family the program generates is worth walking down from the top, because its first member is the one that same essay names as “the same argument one step earlier”.

Drop the variance constraint. Now the program has two equalities — total one, mean $\mu$ — and asks for the most mass above a threshold $t$ for a quantity that cannot be negative. The certificate is a polynomial of degree one, $x/t$, which is at least one above $t$ and at least nought on the positive axis, and its average is $\mu/t$. That is Markov’s inequality.

Complementary slackness locates the extremal distribution. The certificate touches the indicator at $x = 0$ and $x = t$, so the optimum puts mass $\mu/t$ at $t$ and the rest at nought — two points, as the degree predicts. And the bound is attained, so Markov is sharp in exactly the same sense Chebyshev is.

Chebyshev then follows by pointing Markov at the squared deviation, which is the standard derivation and is also a statement about certificates: squaring the variable turns a degree-one certificate into a degree-two one, and the degree is what the extra moment bought. So the two inequalities are one program at two degrees, and the hierarchy continues — each further moment one more constraint, one more degree, one more point in the extremal distribution, and a strictly better bound.

The one thing the hierarchy does not give is a simple answer past the second moment. The degree-three certificate for a two-sided window is already a cubic whose coefficients depend on $k$ in a way nobody writes down, and the extremal distribution has four points. That is why the named inequalities stop at the variance and the rest of the subject changes hypothesis instead of adding moments.

Where the search has to be careful #

The figures compute the optimum by trying every triple of support points and solving the resulting three-by-three system. Two things about that are worth stating, because the first version of the figure got one of them wrong.

The support has to contain the points the answer needs. An even grid on $[-6, 6]$ at forty-one points does not contain $\pm 2$, so the extremal distribution at $\pm 2$ is not representable and the search reports 0.2268 where the answer is 0.25. The grids here include the window’s own edges explicitly, and a figure of this kind that does not is reporting a number about its grid rather than about the question.

And bounding the values does not help. It is tempting to add a third fact — the values lie in a known range — and expect a better bound. For the two-sided tail at exactly $k$ it buys nothing, because the extremal distribution already sits at $\pm k$ and any range containing those points reaches the same answer. A range inside $k$ makes the tail empty, which is a true statement and not a bound. The facts that tighten a bound are the ones that exclude the extremal distribution, and knowing where it sits is what identifies them.

What the program does not do #

It does not scale to the questions people ask. The program has one variable per possible value, so for a continuous quantity it is infinite-dimensional and the search above is a discretisation. The theory handles that — the duality survives, and the extremal distributions are still finitely supported — and the computation does not.

It needs the moments to be exactly known. A bound from an estimated variance is a bound with an error in it, and the program has no place to put that error. In practice the variance is estimated, and the honest version of the bound carries the estimate’s own uncertainty, which is a separate calculation.

And it says nothing about a particular distribution. The optimum is over a whole class, so the answer describes the worst member. Four distributions swept against the bound are all far inside it, and that is the normal state of affairs: the bound is about the class and a distribution in hand deserves its own calculation — which for a sum of many independent pieces is the bell curve’s and is smaller by orders of magnitude.

Where the same duality has already appeared here #

The pattern — an optimisation over a class, and a short certificate that no member does better — is one that has now come up three times here, and the three are worth setting side by side because they are the same theorem in three costumes.

Two numbers that have to meet is the theorem itself: a linear program and its dual reach the same number, and the dual’s variables are the multipliers on the primal’s constraints. Everything on this page is that statement with the primal’s variables being probabilities.

Five weighings and the question is closed is the same duality deciding whether a stable division of a joint gain exists. There the primal is a search over splits, the dual is a family of coalitions with weights, and a failing certificate is a proof of impossibility. Here the primal is a search over distributions and the dual is a polynomial.

In both cases the certificate is what the search cannot supply. A search that finds a distribution proves the bound cannot be lower; a certificate proves it cannot be higher; and the two meeting is the duality. A subject with only the first half reports what it found and cannot say whether it looked hard enough.

The third appearance is the one worth watching for. Whenever a quantity is defined as a supremum or an infimum over a class described by linear conditions, both halves are available — and the certificate is usually the thing somebody had already written down as a proof without noticing it was a dual solution. Chebyshev’s three lines are the clearest example of that in the collection.

What the pictures cannot show #

The searches are over grids of a few dozen points and the question is about all distributions. What the grid can establish is that a particular distribution achieves the bound — which is a lower bound on the optimum — and the certificate is what establishes the upper one. Both halves are in the figures and only together do they pin the answer down.

The certificate is drawn as a curve over the bars, and what makes it a certificate is an inequality at every point of the support rather than the visible fact that the curve is above the line. The figures check the inequality at every grid point, which is the checkable version, and the general statement is the two lines of algebra above.

And the duality itself is not drawn. That the cheapest certificate’s average equals the largest achievable mass is a theorem about two linear programs; the figures compute both sides for the questions they ask and find them equal, which is evidence about those questions and not a proof of the theorem.

Still open: which certificates are worth computing #

The programme extends to almost any question of this shape — several moments, several windows, a constraint on the shape — and the extremal distributions and certificates are computable in each case. What is not settled is which of the resulting bounds are worth having.

The difficulty is that bounds from many moments are sharp and unusable: the certificate is a high-degree polynomial, the extremal distribution has many points, and the resulting expression has no interpretation anybody can carry. So a subject that could in principle compute the exact answer for every hypothesis instead uses a handful of named inequalities, and which handful is a matter of practice rather than theory.

The live technical question concerns constraints that are not moments. A bound over the distributions with a stated mean, variance and unimodal shape is not a linear program in the probabilities — unimodality is not a linear constraint — and the known answers in that setting are obtained by other means and are not known to be sharp in general. The one quoted earlier, a factor of $9/4$ better than Chebyshev for unimodal distributions, is sharp; the corresponding statements for other shape restrictions mostly are not.

What the reframing was worth #

Nothing on this page changes a single number. Chebyshev’s bound is what it was, the extremal distribution is the one that essay exhibits, and Cantelli’s inequality was already named there in a sentence.

What changes is that the bound stops being a discovery and becomes a computation. A three-line proof that happens to be tight is a piece of luck one cannot repeat; a linear program whose dual solution is that proof is a procedure, and pointing it at a new question produces the new question’s bound along with the distribution that meets it and the certificate that proves it.

That is worth carrying past this subject, because the shape recurs. Whenever a bound over a class of objects turns out to be attained, look for the optimisation it solves — and when the constraints are linear, the certificate is guaranteed to exist, to be short, and to be the proof somebody had already found by being clever.