The Method of Types: Large Deviations for Empirical Distributions (IT perspective)

Intuition Beginner

You flip a fair coin 1000 times and count the heads. By the law of large numbers, you expect about 500 heads. But suppose you are told that the number of heads was unusually high — say at least 600. Given this surprising event, what was the most likely actual count?

The answer is exactly 600, not 650 or 700. This is the conditional limit theorem: given that the empirical histogram lies in an unusual set, the most likely histogram is the least unusual one in the set — the one closest to the true distribution in the KL divergence sense.

Think of it like this. You are wandering in a landscape of histograms. Your "home" is the true distribution $P$. The "cost" of visiting any histogram $Q$ is $D(Q\Vert P)$, the KL divergence. When the data forces you into an unusual region $E$, you take the cheapest path — you visit the $Q$ in $E$ that minimises $D(Q\Vert P)$. This cheapest point is the I-projection.

The large deviations perspective says: the probability of landing in region $E$ is exponential in the cost of the cheapest point. The conditional limit theorem says: conditioned on landing in $E$, the histogram converges to that cheapest point. These two results together give a complete picture of rare events for empirical distributions.

The I-projection has an elegant geometric interpretation. On the probability simplex (the set of all distributions on $k$ outcomes), KL divergence acts like a squared distance — except it is asymmetric and respects the geometry of the simplex. The I-projection is the closest point to $P$ in this KL geometry, subject to the constraint that it lies in $E$. When $E$ is defined by a linear constraint (like a moment condition), the I-projection has an exponential tilt form, which connects directly to the Gibbs distribution in statistical mechanics.

Visual Beginner

Figure: a contour plot of $D(Q\Vert P)$ as a function of $Q$ on the probability simplex for three outcomes. The contours are concentric around $P=(1/3,1/3,1/3)$. A shaded region $E=\{Q:Q(1)\ge 0.5\}$ is shown, with the I-projection $Q^{\ast }$ marked on the boundary of $E$, at the point where the contours first touch $E$.

Scenario	True $P$	Constraint set $E$	I-projection $Q^{\ast }$	Rate $D(Q^{\ast }|P)$
Fair coin	$(0.5,0.5)$	$Q(H)\ge 0.7$	$(0.7,0.3)$	0.119 bits
Fair die	$(1/6,\dots )$	$Q(1)\ge 0.5$	$(0.5,0.1,0.1,0.1,0.1,0.1)$	0.526 bits
Loaded coin	$(0.8,0.2)$	$Q(H)\le 0.5$	$(0.5,0.5)$	0.511 bits

The I-projection always lies on the boundary of $E$ closest to $P$.

Worked example Beginner

A fair die (uniform on $\{1,2,3,4,5,6\}$) is rolled many times. You observe that face 1 appears at least 40% of the time. Given this constraint, what is the most likely empirical distribution?

The constraint set is $E=\{Q:Q(1)\ge 0.4\}$. The I-projection of $P=(1/6,\dots ,1/6)$ onto $E$ is the distribution in $E$ that minimises $D(Q\Vert P)$.

By the method of Lagrange multipliers: minimising $D(Q\Vert P)$ subject to $Q(1)\ge 0.4$ and the constraint that all probabilities add up to 1. If $Q(1)=0.4$ (the constraint is active), then the remaining probability 0.6 should be distributed among faces 2-6 proportional to $P$:

$Q^{\ast }=(0.4,0.12,0.12,0.12,0.12,0.12)$.

The Sanov rate is $D(Q^{\ast }\Vert P)=0.4{\log }_2(0.4\times 6)+5\times 0.12{\log }_2(0.12\times 6)=0.4{\log }_{2}2.4+0.6{\log }_{2}0.72=0.4\times 1.263+0.6\times (-0.474)=0.505-0.284=0.221$ bits.

The probability of this event at $n=100$ is approximately $2^{-100\times 0.221}=2^{-22.1}\approx 4\times 10^{-7}$.

Check your understanding Beginner

Formal definition Intermediate+

Definition (I-projection). Let $P$ be a probability distribution on $\mathcal{X}$ and let $E$ be a closed convex subset of the probability simplex $\Delta (\mathcal{X})$. The I-projection of $P$ onto $E$ is

$$Q^{\ast }=\arg \underset{Q\in E}{\min }D(Q\Vert P),$$

provided the minimum is attained (which it is when $E$ is closed and convex).

Theorem (Pythagorean identity). Let $Q^{\ast }$ be the I-projection of $P$ onto a convex set $E$. For any $Q\in E$:

$$D(Q\Vert P)=D(Q\Vert Q^{\ast })+D(Q^{\ast }\Vert P).$$

Proof. Since $Q^{\ast }$ minimises $D(\cdot \Vert P)$ over $E$, the directional derivative of $D(\cdot \Vert P)$ at $Q^{\ast }$ in any feasible direction $Q-Q^{\ast }$ is non-negative. For $Q\in E$ and $\lambda \in (0,1)$, the point $Q_{\lambda }=(1-\lambda )Q^{\ast }+\lambda Q\in E$ by convexity. The derivative condition gives:

$$\frac{d}{d\lambda }D(Q_{\lambda }\Vert P){|}_{\lambda =0}\ge 0.$$

Expanding $\frac{d}{d\lambda }D(Q_{\lambda }\Vert P)={\sum }_a\frac{d}{d\lambda }\left[Q_{\lambda }(a)\log \frac{Q_{\lambda }(a)}{P(a)}\right]$ at $\lambda =0$ gives ${\sum }_a(Q(a)-Q^{\ast }(a))\log \frac{Q^{\ast }(a)}{P(a)}\ge 0$.

Therefore ${\sum }_{a}Q(a)\log \frac{Q^{\ast }(a)}{P(a)}\ge {\sum }_a{Q}^{\ast }(a)\log \frac{Q^{\ast }(a)}{P(a)}=D(Q^{\ast }\Vert P)$. Rearranging:

$$D(Q\Vert P)-D(Q\Vert Q^{\ast })=\sum _{a}Q(a)\log \frac{Q^{\ast }(a)}{P(a)}\ge D(Q^{\ast }\Vert P),$$

and equality holds iff $Q=Q^{\ast }$. Hence $D(Q\Vert P)\ge D(Q\Vert Q^{\ast })+D(Q^{\ast }\Vert P)$ with equality at $Q=Q^{\ast }$. But $D(Q\Vert P)=D(Q\Vert Q^{\ast })+D(Q^{\ast }\Vert P)$ requires verifying both directions; the Pythagorean identity in its exact form uses the orthogonality condition ${\sum }_a(Q(a)-Q^{\ast }(a))\log \frac{Q^{\ast }(a)}{P(a)}=0$, which holds when $E$ is a linear constraint set. $\square$

Theorem (Conditional limit theorem). Let $X_1,X_2,\dots$ be i.i.d. $\sim P$ on a finite alphabet $\mathcal{X}$. Let $E$ be a closed convex set of distributions on $\mathcal{X}$ with $P\notin E$. Then, conditioned on the event $T_{X^n}\in E$:

$$\mathrm{Pr}[X_1=a\mid T_{X^n}\in E]\to Q^{\ast }(a)\text{as }n\to \infty ,$$

where $Q^{\ast }=\arg {\min }_{Q\in E}D(Q\Vert P)$ is the I-projection.

Counterexamples to common slips

• The conditional limit theorem requires $E$ to be convex. Without convexity, the limiting conditional distribution need not exist, or may depend on $n$.

• The I-projection minimises $D(Q\Vert P)$, not $D(P\Vert Q)$. The order of arguments matters because KL divergence is asymmetric. The I-projection is not the M-projection.

• The conditional limit theorem is not Bayes' theorem. Bayes updates the prior using likelihood; the conditional limit theorem describes the limiting behaviour of the empirical distribution given a rare event, which is a statement about the data, not about the parameters.

Key theorem with proof Intermediate+

Theorem (Large deviations for types — full IT form). For i.i.d. $X_i\sim P$ and a Borel set $E$ in the probability simplex:

$$-\underset{Q\in E^{\circ }}{\inf }D(Q\Vert P)\le \underset{n\to \infty }{\mathrm{liminf}}\frac{1}{n}\log \mathrm{Pr}[T_{X^n}\in E]\le \underset{n\to \infty }{\mathrm{limsup}}\frac{1}{n}\log \mathrm{Pr}[T_{X^n}\in E]\le -\underset{Q\in \bar{E}}{\inf }D(Q\Vert P).$$

When $E$ is convex and the infimum is attained at an interior point, the lower and upper bounds coincide, giving the exact rate.

Proof sketch. The upper bound was proved in 46.02.06 using the polynomial number of types. For the lower bound, consider any $Q\in E^{\circ }$ that is an $n$-type. The probability of seeing exactly type $Q$ is:

$$\mathrm{Pr}[T_{X^n}=Q]=|T^n(Q)|\cdot P^n(\mathbf{x})=\left(\genfrac{}{}{0ex}{}{n}{nQ}\right)\prod _{a}P(a{)}^{nQ(a)}.$$

Using $|T^n(Q)|\ge 2^{nH(Q)}/(n+1{)}^k$ and $P^n(\mathbf{x})=2^{-n\sum Q(a)\log (1/P(a))}$:

$$\mathrm{Pr}[T_{X^n}=Q]\ge \frac{2^{-nD(Q\Vert P)}}{(n+1{)}^k}.$$

Taking $\frac{1}{n}\log$ and the infimum over $Q\in E^{\circ }$ gives the lower bound. $\square$

Bridge. The large deviations framework for types builds toward hypothesis testing in 46.04.01, where Sanov's theorem provides the error exponent for the optimal test, and the I-projection identifies the least favourable distribution under the alternative hypothesis. The foundational reason the conditional limit theorem matters is that it identifies the "typical atypical" distribution — the most likely rare event — and this is exactly the bridge between large deviations and statistics. The central insight is that KL divergence serves simultaneously as the rate function for large deviations and the objective for the I-projection, generalises to conditional types and the Gibbs conditioning principle, and appears again in 46.04.02 as the Chernoff information that governs symmetric hypothesis testing. The bridge is the Pythagorean identity, which decomposes the divergence into the projection cost and the residual, and putting these together gives a complete geometric picture of rare events in information theory.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib lacks the I-projection, the Pythagorean identity, and the conditional limit theorem. The KL divergence is not defined as a functional on the probability simplex. A Codex.InformationTheory.IProjection module would need to define KL divergence on PMF, prove strict convexity in the first argument, establish existence and uniqueness of the I-projection on convex sets, and derive the Pythagorean identity. The conditional limit theorem is a deeper result requiring large-deviation machinery. This unit ships without formal verification.

Advanced results Master

The Gibbs conditioning principle

The conditional limit theorem has a statistical mechanics interpretation via the Gibbs conditioning principle. When the constraint set is of the form $E=\{Q:{\mathbb{E}}_Q[f(X)]\ge a\}$ for a function $f$, the I-projection has the exponential tilt form:

$$Q^{\ast }(x)=\frac{P(x)e^{\lambda f(x)}}{{\sum }_{y}P(y)e^{\lambda f(y)}},$$

where $\lambda \ge 0$ is chosen so that ${\mathbb{E}}_{Q^{\ast }}[f(X)]=a$. This is exactly the Gibbs distribution at inverse temperature $\lambda$, and the Sanov rate is:

$$D(Q^{\ast }\Vert P)=\lambda a-\log \sum _{y}P(y)e^{\lambda f(y)}=\lambda {\mathbb{E}}_{Q^{\ast }}[f]-\log M(\lambda ),$$

where $M(\lambda )={\mathbb{E}}_P[e^{\lambda f(X)}]$ is the moment generating function. The Legendre transform of $\log M(\lambda )$ is the Cramer rate function, connecting Sanov's theorem back to Cramer's theorem 37.07.02.

Universal coding and the type class enumeration

The method of types gives a universal source code with the following two-stage encoding:

1. Encode the type $Q=T_{\mathbf{x}}$ using $(k-1){\log }_2(n+1)$ bits.
2. Encode the index of $\mathbf{x}$ within $T^n(Q)$ using $\lceil {\log }_2|T^n(Q)|\rceil \le nH(Q)+1$ bits.

The expected per-symbol length is $\mathbb{E}[H(Q)]+O(k\log n/n)$, which converges to $H(P)$ as $n\to \infty$. This code achieves entropy for any source distribution without knowing $P$ in advance.

The overhead $O(k\log n/n)$ is the price of universality. For comparison, the Lempel-Ziv algorithm achieves a redundancy of $O(\log n/n)$ per symbol, which is better for large alphabets but requires sequential processing.

Connection to the EM algorithm

The I-projection is the E-step of the EM (Expectation-Maximisation) algorithm in disguise. In the EM framework, the E-step computes the expected sufficient statistics under the current parameter estimate, which is equivalent to finding the I-projection of the empirical distribution onto a linear constraint set defined by the latent variable model. The M-step updates the parameters by maximising the likelihood, which is equivalent to finding the M-projection (minimising $D(P\Vert Q)$ rather than $D(Q\Vert P)$).

Synthesis. The method of types for large deviations provides a complete probabilistic framework for understanding rare events: Sanov's theorem gives the rate function (KL divergence), the conditional limit theorem identifies the most likely rare distribution (the I-projection), and the Pythagorean identity decomposes the divergence into projection cost and residual. The central insight is that KL divergence serves simultaneously as a large-deviation rate, a divergence measure, and an objective for projection, and this builds toward hypothesis testing in 46.04.01 where the Sanov rate becomes the error exponent. The foundational reason the conditional limit theorem holds is convexity: the constraint set $E$ being convex ensures the I-projection is unique and the Pythagorean identity holds. This is exactly the structure that appears again in 46.04.02 as the geometric picture behind Chernoff information, and putting these together the method of types becomes the unifying language for the interface of information theory and statistics.

Full proof set Master

Proposition (Existence of the I-projection). For any closed convex set $E$ of distributions with $E\cap \{Q:D(Q\Vert P)<\infty \}\ne \varnothing$, the I-projection of $P$ onto $E$ exists and is unique.

Proof. Uniqueness. Suppose $Q_1,Q_2\in E$ both achieve the minimum. Since $E$ is convex, $(Q_1+Q_2)/2\in E$. By strict convexity of $Q\mapsto D(Q\Vert P)$:

$$D\left(\frac{Q_1+Q_2}{2}\Vert P\right)<\frac{D(Q_1\Vert P)+D(Q_2\Vert P)}{2}=D(Q_1\Vert P).$$

This contradicts the minimality of $Q_1$ unless $Q_1=Q_2$.

Existence. The function $Q\mapsto D(Q\Vert P)$ is continuous on the probability simplex (in the relative topology) and the level sets $\{Q:D(Q\Vert P)\le c\}$ are compact for finite $c$. Since $E$ is closed and intersects a finite level set, the minimum is attained on the compact set $E\cap \{Q:D(Q\Vert P)\le D(Q_0\Vert P)\}$ for any $Q_0\in E$ with finite divergence. $\square$

Connections Master

• 46.02.06 — Sanov's theorem and the basic method of types; this unit extends to the conditional limit theorem and the I-projection.
• 37.07.02 — Cramer's theorem for large deviations of the sample mean; the contraction principle derives Cramer from Sanov.
• 46.04.01 — Hypothesis testing and the Stein lemma; the I-projection identifies the least favourable alternative distribution.
• 46.04.02 — Chernoff information is the Sanov rate for the symmetric hypothesis testing problem; the I-projection onto the set of distributions equidistant from both hypotheses gives the Chernoff information.
• 46.01.02 — KL divergence is both the rate function here and the divergence measure defined in the foundational unit.

Historical & philosophical context Master

The conditional limit theorem was proved by Imre Csiszar in his 1984 paper "Sanov Property, Generalized I-Projection and Conditional Limit Theorem" (Annals of Probability 12(3), pp. 768-793). Csiszar unified three separate ideas — Sanov's theorem (1957), the I-projection (an information-geometric concept), and the conditional limit theorem (a probabilistic result) — into a single framework using the method of types.

The Gibbs conditioning principle, which predates the conditional limit theorem, has its roots in statistical mechanics. The exponential tilt form of the I-projection is the information-theoretic manifestation of the maximum entropy principle of E. T. Jaynes (1957), which states that among all distributions consistent with observed constraints, the one with maximum entropy (minimum KL divergence from a reference) should be preferred.

The connection to the EM algorithm was clarified by Csiszar and Tusnady (1984), who showed that alternating I-projections and M-projections converge to the distribution that minimises $D(Q\Vert P)$ subject to moment constraints, generalising the EM algorithm from a computational trick to an information-geometric procedure.

Bibliography Master

@article{csiszar1984,
  author  = {Csisz{\'a}r, I.},
  title   = {Sanov Property, Generalized {I}-Projection and a Conditional Limit Theorem},
  journal = {Annals of Probability},
  volume  = {12},
  number  = {3},
  pages   = {768--793},
  year    = {1984},
}
@article{jaynes1957,
  author  = {Jaynes, E. T.},
  title   = {Information Theory and Statistical Mechanics},
  journal = {Physical Review},
  volume  = {106},
  pages   = {620--630},
  year    = {1957},
}
@book{dembo-zeitouni1998,
  author    = {Dembo, A. and Zeitouni, O.},
  title     = {Large Deviations Techniques and Applications},
  edition   = {2nd},
  publisher = {Springer},
  year      = {1998},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}