When the whole histogram deviates

The tail is not a bell asked for the chance that an average lands a fixed distance from where it should, and found that the answer dies exponentially at a rate computed from the summand. The average is one number. Roll a three-sided die twelve times and there is much more on the table than the average: there is the whole tally of how often each face came up, and the average is a single summary of it.

Asking for the chance that the tally comes out wrong turns out to be the more natural question, and the more informative answer. The rate is no longer a function on the real line. It is a function on the space of distributions, and everything the rung below computed is a shadow of it.

Finitely many histograms #

The first thing to notice about the picture is that it is finite. A sequence of twelve draws over three faces is one of $3^{12}$ things, which is 531,441; the tally of such a sequence is a triple of whole numbers adding to twelve, and there are only ninety-one of those.

That gap is the whole method. The number of tallies — the number of types, in the standard vocabulary — grows like a polynomial in the number of draws, while the number of sequences grows exponentially. So a sum over types is a sum over polynomially many terms, each of which is exponentially small, and a sum like that is controlled by its largest term to within a factor that does not matter on the exponential scale.

The chance of one particular tally is an ordinary multinomial coefficient times a product of the face chances, and there is a clean way to write it. If the true chances are $q$ and the tally, read as a distribution, is $p$, then the chance of that tally is

$$e^{-n \, D(p \Vert q)}$$

to within a polynomial factor, where $n$ is the number of draws and $D$ is the relative entropy of $p$ against $q$:

$$D(p \Vert q) = \sum_i p_i \log \frac{p_i}{q_i}.$$

Both the upper and the lower bound are checked on every tally in the figures above, at every parameter they are drawn at — not the leading behaviour, the actual inequality, for all ninety-one and all 325.

Relative entropy is not a distance, and behaves like one #

$D(p \Vert q)$ is zero when $p$ and $q$ agree and positive otherwise, and it grows as the two pull apart. That is enough to make the exponent above say what it should: a tally equal to the truth is not unlikely at all, and a tally far from the truth is exponentially unlikely, with the exponent growing with the number of draws.

It is not a distance. It is not symmetric — $D(p \Vert q)$ and $D(q \Vert p)$ are different numbers, and dramatically so when $q$ gives some outcome a very small chance — and it does not satisfy the triangle inequality. Both failures are the right behaviour rather than defects. Asking how surprising a fair-looking tally is under a loaded die is a different question from asking how surprising a loaded-looking tally is under a fair one, and a symmetric quantity could not tell them apart.

The asymmetry has a sharp consequence: if $q$ assigns an outcome probability zero and $p$ does not, then $D(p \Vert q)$ is infinite, which is correct — that tally cannot occur at all, and no number of draws makes it occur. The reverse is finite. The information content of one observation is the same quantity read as a coding cost, and the asymmetry is there too: coding a source with the wrong model costs extra bits, and how many depends on which model is the wrong one.

From a region to a number #

Now the theorem. Take a set of distributions — say, all the tallies whose average is at least some value — and ask for the chance that the tally lands in it. That chance is a sum of the individual chances, each of which is $e^{-nD}$ up to a polynomial. Polynomially many terms, each exponentially small: the sum is dominated by the largest term, which is the one with the smallest relative entropy in the set. So

$$-\frac{1}{n} \log \Pr[\text{tally in } A] \longrightarrow \min_{p \in A} D(p \Vert q),$$

which is Sanov’s theorem. The rate at which a rare event dies is the relative entropy of the nearest point of the event to the truth.

The picture is the theorem being watched rather than argued. At each number of draws the probability is computed exactly — a finite sum over the tallies in the region, in ordinary arithmetic — and divided into the exponent. The horizontal line was found separately, by sweeping the region for its lowest relative entropy. Neither number is used to produce the other.

Why this contains the rung below #

Cramér’s theorem, from the previous rung, gives the rate at which a rare average dies, as a Legendre transform of the summand’s moment generating function. That looks like a different object entirely, and it is the same object with a constraint on it.

The set of tallies whose average is at least $a$ is a region of the simplex. Minimising relative entropy over that region — a constrained minimisation with one linear constraint — is a Lagrange-multiplier problem, and its answer is exactly the Legendre transform Cramér’s theorem writes down. So the rate for a rare average is the relative entropy of the closest distribution having that average, and the multiplier is Cramér’s tilting parameter.

That is the payoff for asking the bigger question. Cramér’s rate function is a formula whose shape has to be taken on faith; Sanov’s is a distance, and the formula is what falls out when the distance is minimised subject to a constraint. The tilted distribution, which appears in the earlier essay as a device, is here the answer to a minimisation — the point of the region nearest the truth.

The conditional limit, which is the surprising part #

There is a consequence that has nothing to do with rates and is worth the whole theorem on its own.

Suppose the rare event happens: the twelve draws really did average at least 2.4. What does the tally look like? Not like the truth, since the truth is excluded. Not like the extreme case either. It looks like the minimiser — the distribution in the region closest to the truth — and it looks like that with probability approaching one.

The reason is the same domination argument read a second time. The chance of the event is a sum over the tallies inside it, dominated by the nearest one; so conditional on the event, the chance of being at any other tally is exponentially smaller than the chance of being at the nearest, and everything but the minimiser washes out. A conditioned system does not do the least it can get away with in some vague sense; it lands on a specific distribution, and the distribution is computable.

This is the mathematical content of a physical habit of thought: a system constrained to an unusual energy adopts the distribution of least relative entropy subject to that energy, which is the Boltzmann distribution. The tilting in the figure above is that distribution, and its exponential shape is the shape of a Lagrange multiplier rather than an assumption about physics.

Two counts, and why they have to agree #

There is a check available here that is worth performing because it is the sort of thing that catches a wrong exponent, and it is the reason the figures compute what they do.

The chance of every tally, added over all of them, is one. That is a statement about ninety-one numbers, and it is checked in the figure at every parameter it is drawn at. It has to hold, and it is not automatic: the multinomial coefficients and the face chances have to be combined in exactly the right way, and a figure that got the coefficient wrong would still draw a plausible-looking cloud of shaded dots.

The second check is the pair of bounds. Every tally’s chance is at most $e^{-nD}$ and at least $e^{-nD}$ divided by a polynomial in $n$ — the polynomial being the number of tallies, near enough. Those two inequalities are what the whole theorem rests on, and they are checked on each of the ninety-one rather than on a sample of them. This is the same discipline the counting of colourings runs on: an identity that holds because two counts of one collection must agree is only an argument once both counts have been made.

The upper bound is the interesting half. It says no tally is more likely than $e^{-nD}$, which for the true distribution itself means the chance of getting the exact truth is at most one — true, and uninformative. For a tally far from the truth the same inequality is the whole content, and the reason it holds is that the multinomial coefficient counting sequences with that tally is at most $e^{nH(p)}$, where $H$ is the entropy. Counting sequences and bounding probabilities turn out to be the same computation with the logarithm moved.

What it costs #

The exponent throws away everything but the exponent. Sanov’s theorem is a statement about $-\frac{1}{n}\log$ of a probability, so it is blind to polynomial factors, and the plot above shows exactly that: the measured exponent is still visibly above the limit at ninety draws, because the polynomial has not finished shrinking. For a probability of $10^{-8}$, being wrong by a factor of a hundred is invisible on this scale and may be the whole answer somebody wanted.

The convergence is slow where the geometry is flat. The domination argument is only as good as the gap between the nearest point of the region and the next, and where the region’s boundary is nearly tangent to a level set of relative entropy, several tallies contribute comparably and the polynomial factor is larger.

It needs finitely many outcomes to be this easy. The method of types counts tallies, and a die with three faces has polynomially many. For a continuous distribution the argument is a limit of this one, with the type classes replaced by neighbourhoods in a topology on distributions, and the resulting statement — the general Sanov theorem — is true and considerably harder to prove.

Where it fails, and what it needs #

The set has to be reasonable. As stated, the theorem needs the closure of the region’s interior to be the region itself, or the upper and lower bounds settle on different numbers. A region consisting of a single distribution has probability zero for most $n$ and an infimum of relative entropy that is finite — the statement fails, and it fails for a bookkeeping reason rather than a deep one.

The truth has to have full support, or the infinities have to be handled. If $q$ misses an outcome that the region requires, the rate is infinite, and the theorem correctly says the probability is zero rather than merely small.

And it is a statement about the limit. Nothing above bounds the probability at a stated $n$; the exact sums in the figures do that, and they do it by exhausting the region, which is available here because the die has three faces and the tallies can be listed.

Where it came from #

Sanov proved his theorem in 1957, for a finite alphabet. The proof by counting types is Csiszár’s and Körner’s, from the information-theory tradition of the 1970s and 1980s, and it is the one drawn here because it is the one that makes the polynomial factor explicit — the whole argument is there are few tallies and each is exponentially unlikely, and both halves are counts.

The order of discovery is the reverse of the order of generality, which happens often. Cramér’s theorem came first, in 1938, about averages; Sanov’s is more general and arrived nineteen years later; and the modern treatment derives Cramér from Sanov by a constrained minimisation, so the later, larger theorem is now the starting point. The pattern is worth noticing because it recurs: the special case is found first because it is what somebody needed, and the general case is found later because it is what the special case turns out to be about.

What the pictures cannot show #

The simplex drawn here has three corners because three is the largest number of outcomes that fits on a page. Everything said above holds for any finite alphabet, and the picture for five outcomes is a four-dimensional simplex that cannot be drawn at all — so the figure is an instance rather than the statement.

The shading is relative entropy, and it is banded into five levels because a continuous shading would not survive being read. The bands are a rendering choice; the numbers behind them are exact.

And the plot of the exponent stops at ninety draws, which is where exact enumeration becomes slow. It shows a sequence approaching a line and it does not show the sequence reaching the line, because the sequence never does — the limit is a limit, and a picture of a limit is always a picture of some of its terms.

The ladder from here #

Below: the tail is not a bell, which is this theorem with a single constraint imposed, and bell curve from coin flips, which is the window where none of this applies because the deviation shrinks with $n$. Sideways: one point’s worth of information, where the same relative entropy is a coding cost, and how far from the average a thing can be, whose bounds hold at every $n$ rather than in the limit. Above: the general Sanov theorem on abstract spaces, Gibbs conditioning, and the contraction principle that produces one rate function from another.

What is worth carrying away #

Asking a bigger question can make the answer simpler. The chance that an average is unusual has a rate function that is a Legendre transform, and there is no reading of it that makes it obvious. The chance that a whole tally is unusual has a rate that is a distance, and the distance says what it means: how many times more surprising this tally is under the truth than under itself.

Everything narrower is then a minimisation. That is the shape to look for whenever a formula seems to work without saying why — it is often a constrained optimum of something with an interpretation, and finding the something is the explanation.