Method of Types & Sanov's Theorem

Type-counting turns large deviations into relative-entropy minimization.

The idea

The method of types computes the exponential rate at which rare empirical patterns become unlikely — for example, the probability that a hundred rolls of a fair die average at least $4$.

The type of a sequence $x^{n}$ is its empirical distribution $P_{x^{n}}$: the fraction of the sequence equal to each symbol. Two facts carry the method. First, there are at most $(n+1)^{|\mathcal{X}|}$ types — polynomially many, since a type is determined by $|\mathcal{X}|$ counts — while there are exponentially many sequences. Second, the probability of a whole type class is governed by relative entropy.

Lemma (Probability of a type class).

Under an i.i.d. source $Q$, the type class $T(P)$, the set of sequences of type $P$, has probability $Q^{n}\bigl(T(P)\bigr) \doteq 2^{-n\,D(P \| Q)},$ where $D(P \| Q) = \sum_{x} P(x)\log_{2}\frac{P(x)}{Q(x)}$ is the relative entropy in bits and $\doteq$ means the two sides agree in their exponential rate, up to polynomial factors.

Because there are only polynomially many types, summing over them changes no exponential rate, and the type of smallest divergence dominates. That is the content of Sanov's theorem.

Theorem (Sanov's theorem).

Let $Q$ be an i.i.d. source on a finite alphabet and let $E$ be a set of distributions on that alphabet. The probability that the empirical distribution of $n$ samples lies in $E$ satisfies $Q^{n}(E) \doteq 2^{-n\,\min_{P \in E} D(P \| Q)}.$

The rate is set by the distribution $P^{*} \in E$ closest to the source $Q$ in relative entropy, which the figure shows as a projection of $Q$ onto $E$.

Ways to work on it

• Walkthrough. Counting types, the type-class probability, and the relative-entropy rate.
• Practice. Relative-entropy decay rate of a binary type class under a source.
• Hardest. Apply Sanov's theorem to find a large-deviation rate.

Not sure where to start? Take the ten-question placement test.