46.02.06 · information-theory / 02-source-coding

The Method of Types and Sanov's Theorem (IT formulation)

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §11.1-11.5; Csiszar 1998 The Method of Types IEEE Trans. Info. Theory 44(6) 2505-2523; Dembo & Zeitouni 1998 Large Deviations Techniques and Applications 2e (Springer) §2.1-2.3

Intuition Beginner

Flip a coin 100 times. You get some number of heads — say 47. The "type" of the sequence is just the histogram: 47 heads, 53 tails. Two sequences have the same type if they have the same histogram, regardless of the order of outcomes.

There are $2^{100}$ possible sequences but only 101 possible types (0 heads, 1 head, ..., 100 heads). That is a huge collapse. Most types are boring — they cluster near 50 heads, 50 tails. The surprising types (like 0 heads) are extremely rare.

How many sequences share a given type? If the type says 50 heads and 50 tails, the number of such sequences is "100 choose 50", which is enormous — roughly $2^{100}$ divided by the square root of $50 π$ . If the type says 0 heads, there is only one sequence (all tails).

Sanov's theorem answers a deeper question. Suppose the coin is fair, and you ask: what is the probability that the empirical histogram lands in some unusual set, like "at least 70 heads out of 100"? The answer is exponential in $n$ , with the rate given by a KL divergence. The least-unusual histogram in the set (in this case, exactly 70-30) determines the rate, and that rate is $D (Q ∥ P)$ where $Q = (0.7, 0.3)$ and $P = (0.5, 0.5)$ .

The method of types reframes Sanov's theorem in purely combinatorial language. No integrals, no measure theory — just counting sequences and bounding multinomial coefficients. This combinatorial clarity makes it the preferred tool in information theory.

The method of types has a philosophical implication: it separates the combinatorial structure of the problem (how many sequences have a given type) from the probabilistic structure (how likely each sequence is under the true distribution). The combinatorial part is governed by entropy, and the probabilistic part by KL divergence. These two quantities are the pillars of information theory, and the method of types shows exactly how they interact.

Visual Beginner

Figure: a grid of 100 cells, each coloured black (heads) or white (tails). Three panels show: (1) a typical sequence with 48 heads and 52 tails, scattered randomly; (2) a type class showing all rearrangements of the same histogram are equally likely; (3) an atypical sequence with 90 heads and 10 tails, concentrated black.

Sequence type	Number of heads	Number of such sequences	Probability (fair coin)
50-50	50	$(50 100) \approx 1 0^{29}$	about 0.08
60-40	60	$(60 100) \approx 1 0^{28}$	about 0.011
70-30	70	$(70 100) \approx 1 0^{25}$	about 0.00002
90-10	90	$(90 100) \approx 1 0^{13}$	extremely small
100-0	100	1	$2^{- 100}$

The number of sequences drops precipitously as the type becomes more extreme, and the probability drops even faster because each individual sequence has probability $2^{- 100}$ .

Worked example Beginner

A fair die is rolled 12 times. The type of the outcome sequence is the count of each face (1 through 6). How many sequences have type $(3, 2, 2, 2, 2, 1)$ — meaning three 1s, two each of 2 through 5, and one 6?

The count is a multinomial coefficient: the number of ways to arrange 12 items where three are of one kind, two each of four kinds, and one of the last kind.

The answer is $12! / (3! \times 2! \times 2! \times 2! \times 2! \times 1!) = 479001600/ (6 \times 2 \times 2 \times 2 \times 2 \times 1) = 479001600/96 = 4989600$ .

Each such sequence has probability $(1/6)^{12}$ because the die is fair. So the probability of seeing exactly this type is $4989600 \times (1/6)^{12} \approx 0.0032$ .

Compare with the most likely type, $(2, 2, 2, 2, 2, 2)$ : the count is $12! / (2!)^{6} \approx 7.5 \times 1 0^{6}$ , and the probability is about $0.0049$ . The difference is small because 12 is a short sequence. For $n = 1000$ , the concentration around the uniform type would be much sharper.

Check your understanding Beginner

Formal definition Intermediate+

Let $X$ be a finite alphabet with $∣ X ∣ = k$ and let $X^{n} = (X_{1}, \dots, X_{n})$ be an i.i.d. sequence with $X_{i} \sim P$ on $X$ .

Definition (Type). The type (or empirical distribution) of a sequence $x = (x_{1}, \dots, x_{n}) \in X^{n}$ is the probability distribution $T_{x}$ on $X$ defined by

T_{x} (a) = \frac{1}{n} i = 1 \sum n 1 [x_{i} = a], a \in X .

A distribution $Q$ on $X$ is called an $n$ -type if $n Q (a) \in {0, 1, 2, \dots}$ for all $a$ .

Definition (Type class). The type class of a distribution $Q$ is

T^{n} (Q) = {x \in X^{n} : T_{x} = Q} .

Definition (Probability under $P$ ). For any $n$ -type $Q$ and true distribution $P$ ,

P^{n} (T^{n} (Q)) = (n Q n) a \in X \prod P (a)^{n Q (a)} .

Counterexamples to common slips

Types are distributions on the source alphabet, not on the integers. The type $T_{x}$ lives in the probability simplex $Δ (X)$ , not in $X$ itself.
Sanov's theorem is a large-deviation result, not a limit theorem. It gives the exponential rate at which probabilities vanish, not the limiting distribution. The limiting distribution of the type is the true distribution $P$ (by the law of large numbers); Sanov quantifies the exponentially rare deviations.
The infimum in Sanov's theorem is over the closure of the set $E$ . For open sets, the equality is exact ( $≐$ ); for closed sets, the upper and lower bounds match. For general sets, taking the interior and closure gives two-sided bounds.

Key theorem with proof Intermediate+

Theorem (Sanov's theorem, IT formulation). Let $X_{1}, X_{2}, \dots$ be i.i.d. $\sim P$ on a finite alphabet $X$ . Let $E$ be a set of probability distributions on $X$ . Then

Pr [T_{X^{n}} \in E] ≐ 2^{- n i n f_{Q \in E} D (Q ∥ P)},

where $≐$ denotes equality to first order in the exponent: $lim_{n \to \infty} \frac{1}{n} lo g_{2} Pr [T_{X^{n}} \in E] = - in f_{Q \in E} D (Q ∥ P)$ .

Proof sketch. We prove the upper bound; the lower bound follows by restricting to a single type.

Upper bound. The number of types is at most $(n + 1)^{∣ X ∣ - 1}$ , which is polynomial in $n$ . For each type $Q \in E$ ,

P^{n} (T^{n} (Q)) = (n Q n) a \prod P (a)^{n Q (a)} \leq 2^{n H (Q)} \cdot 2^{- n \sum_{a} Q (a) l o g_{2} (1/ P (a))} = 2^{- n D (Q ∥ P)} .

Summing over all types in $E$ :

Pr [T_{X^{n}} \in E] = Q \in E \cap P_{n} \sum P^{n} (T^{n} (Q)) \leq (n + 1)^{k - 1} \cdot 2^{- n i n f_{Q \in E} D (Q ∥ P)} .

Since $(n + 1)^{k - 1}$ is polynomial in $n$ , it does not affect the exponential rate:

\frac{1}{n} lo g_{2} Pr [T_{X^{n}} \in E] \leq - Q \in E in f D (Q ∥ P) + \frac{( k - 1 ) lo g _{2} ( n + 1 )}{n} \to - Q \in E in f D (Q ∥ P) .

Lower bound. For any $Q^{*} \in ar g in f_{Q \in E} D (Q ∥ P)$ that is an $n$ -type (or can be approximated by $n$ -types):

P^{n} (T^{n} (Q^{*})) = (n Q ^{*} n) a \prod P (a)^{n Q^{*} (a)} \geq \frac{2 ^{n H (Q^{*})}}{( n + 1 ) ^{k}} \cdot 2^{- n \sum_{a} Q^{*} (a) l o g_{2} (1/ P (a))} = \frac{2 ^{- n D (Q^{*} ∥ P)}}{( n + 1 ) ^{k}} .

Therefore $\frac{1}{n} lo g_{2} Pr \geq - D (Q^{*} ∥ P) - \frac{k l o g _{2} ( n + 1 )}{n} \to - D (Q^{*} ∥ P)$ . $□$

Bridge. The method of types builds toward universal source coding in this same unit, where the type class size bound $∣ T^{n} (Q) ∣ \approx 2^{n H (Q)}$ directly controls the rate of a code that achieves entropy without knowing the true distribution. This is exactly the combinatorial mechanism that makes the two-stage code (describe the type, then describe the sequence within the type class) achieve the entropy rate with overhead that vanishes per symbol. The foundational reason Sanov's theorem matters for information theory is that KL divergence appears as both the large-deviation rate function here and the redundancy of mismatched codes in 46.02.03, and the bridge is the counting argument that connects combinatorial type classes to exponential probabilities. The central insight generalises to conditional types and the method of types for channel coding in 46.04.03, where Sanov's theorem governs the error exponents, and appears again in 46.04.01 as the engine behind the Stein lemma.

Exercises Intermediate+

Exercise (medium, short answer).

Prove that the size of the type class $T^{n} (Q)$ satisfies

\frac{1}{( n + 1 ) ^{k}} 2^{n H (Q)} \leq ∣ T^{n} (Q) ∣ \leq 2^{n H (Q)} .

Hint

Upper bound: the number of sequences with type $Q$ is the multinomial coefficient $(n Q n)$ . Use the bound $(n Q n) \leq 2^{n H (Q)}$ from the entropy of the multinomial.

Lower bound: use the exact formula $(n Q n) \geq \frac{n ^{n}}{\prod _{a} ( n Q ( a ) ) ^{n Q (a)}} / C$ for a polynomial correction $C$ .

Answer

Upper bound. $∣ T^{n} (Q) ∣ = (n Q n)$ , the multinomial coefficient. The multinomial theorem gives $\sum_{Q} (n Q n) \prod P (a)^{n Q (a)} = (\sum P (a))^{n} = 1$ for the distribution $P$ that assigns probability $2^{- l_{a}}$ with $l_{a} = - lo g_{2} Q (a)$ (approximately). More directly, $(n Q n) \leq \frac{n ^{n}}{\prod _{a} ( n Q ( a ) ) ^{n Q (a)}} = 2^{n H (Q)}$ by Stirling's approximation.

Lower bound. Stirling gives $(n Q n) \geq \frac{2 ^{n H (Q)}}{( n + 1 ) ^{k}}$ because the Stirling correction $2 π n Q (a)$ contributes at most a polynomial factor $(n + 1)^{k}$ when accumulated over all $k$ symbols.

Exercise (hard, short answer).

Prove that the number of types for sequences of length $n$ over an alphabet of size $k$ is at most $(n + 1)^{k - 1}$ .

Answer

A type is a probability distribution $(q_{1}, \dots, q_{k})$ with $q_{i} = n_{i} / n$ for non-negative integers $n_{i}$ summing to $n$ . This is equivalent to distributing $n$ indistinguishable balls into $k$ bins. The count is $(k - 1 n + k - 1)$ . By the bound $(k - 1 n + k - 1) \leq (n + 1)^{k - 1}$ (since each of the $k - 1$ "dividers" can be placed in at most $n + 1$ positions), the result follows.

More precisely, $(k - 1 n + k - 1) = \frac{( n + k - 1 )!}{n ! ( k - 1 )!} \leq \frac{( n + k - 1 ) ^{k - 1}}{( k - 1 )!} \leq (n + 1)^{k - 1}$ for $k \leq n + 1$ (and the bound $(n + 1)^{k - 1}$ always holds as a generous upper bound since there are at most $n + 1$ choices for each of the first $k - 1$ values $n_{1}, \dots, n_{k - 1}$ , with $n_{k} = n - n_{1} - \dots - n_{k - 1}$ determined).

Lean formalization Intermediate+

Mathlib lacks the type-theoretic machinery for the method of types. There is no definition of empirical distribution as a map from $X^{n}$ to the probability simplex, no type-class size bounds, and no Sanov's theorem. The multinomial coefficient exists via Finset.ncard and combinatorial identities, but the information-theoretic bounds connecting type-class size to entropy are absent. A Codex.InformationTheory.MethodOfTypes module would need to define the type operator, prove the size bounds using Stirling's approximation, and derive Sanov's theorem as a corollary. This unit ships without formal verification.

Advanced results Master

Conditional types and the conditional method of types

The method of types extends to pairs of sequences. Given sequences $x \in X^{n}$ and $y \in Y^{n}$ , the joint type is $T_{x, y}$ and the conditional type $T_{y ∣ x}$ is the collection of transition counts from each $x$ to each $y$ .

The conditional type class $T_{x}^{n} (V)$ (the set of $y$ with given conditional type $V$ given $x$ ) has size approximately $2^{n H (V ∣ T_{x})}$ , paralleling the unconditional bound. This gives a Sanov-type theorem for conditional distributions:

Pr [T_{Y^{n} ∣ X^{n}} \in E ∣ X^{n} = x] ≐ 2^{- n i n f_{V \in E} D (V ∥ W ∣ T_{x})},

where $W$ is the true conditional distribution and $D (V ∥ W ∣ P) = \sum_{x} P (x) D (V (\cdot ∣ x) ∥ W (\cdot ∣ x))$ .

Universal source coding

The two-stage code (type header + sequence index within type class) achieves the entropy rate for any source distribution without knowing $P$ in advance. The per-symbol redundancy is $O (k lo g n / n)$ , which vanishes as block length grows.

This universality result is the information-theoretic analogue of the minimum description length (MDL) principle: the best model for the data is the one that minimises the total description length, which is the sum of the model complexity (the type header) and the data complexity given the model (the sequence index).

Connections to large deviations theory

Sanov's theorem in the IT formulation is equivalent to Cramer's theorem 37.07.02 for the empirical mean, but stated in the stronger topology of distributions rather than means. The contraction principle in large deviations theory says that if $T_{X^{n}}$ satisfies a large deviation principle with rate function $D (\cdot ∥ P)$ , then the image $f (T_{X^{n}})$ satisfies a large deviation principle with rate function $in f {D (Q ∥ P) : f (Q) = z}$ .

This contraction principle directly yields Cramer's theorem: the empirical mean $\overset{ˉ}{X}_{n} = \sum X_{i} / n$ is a function of the type, and the rate function for $\overset{ˉ}{X}_{n}$ is $in f {D (Q ∥ P) : E_{Q} [X] = z}$ , which by Lagrangian duality equals the Legendre transform $Λ^{*} (z)$ of the cumulant generating function.

The I-projection and Sanov's theorem for convex sets

When $E$ is convex, the minimiser $Q^{*} = ar g in f_{Q \in E} D (Q ∥ P)$ is unique and is called the I-projection of $P$ onto $E$ . The I-projection satisfies a Pythagorean identity: for any $Q \in E$ ,

D (Q ∥ P) = D (Q ∥ Q^{*}) + D (Q^{*} ∥ P) .

This identity is the foundation of iterative proportional fitting (IPF) and the iterative algorithms for computing maximum-entropy distributions subject to linear constraints.

Synthesis. The method of types collapses exponential-sized sequence spaces into polynomial-sized type classes, with type-class size governed by entropy; Sanov's theorem identifies KL divergence as the rate function for large deviations of the empirical distribution. The central insight builds toward universal source coding where the type-class size bound directly controls the overhead of codes that achieve entropy without knowing the distribution. This is exactly the bridge between combinatorics and probability that makes information theory cohere: entropy counts sequences, KL divergence measures how unlikely a type is, and the polynomial number of types makes the counting tractable. The method of types generalises to conditional types and the I-projection, appears again in 46.04.01 as the engine behind the Stein lemma, and putting these together yields a unified combinatorial framework for all of large-deviation information theory.

Full proof set Master

Proposition (Type class size bounds). For any $n$ -type $Q$ on an alphabet of size $k$ :

\frac{2 ^{n H (Q)}}{( n + 1 ) ^{k}} \leq ∣ T^{n} (Q) ∣ \leq 2^{n H (Q)} .

Proof. The size of the type class is the multinomial coefficient $∣ T^{n} (Q) ∣ = (n Q n)$ .

Upper bound. By the entropy bound on multinomial coefficients:

(n Q n) = \frac{n !}{\prod _{a} ( n Q ( a ))!} \leq a \prod \frac{n ^{n Q (a)}}{( n Q ( a ) ) ^{n Q (a)}} = \frac{n ^{n}}{\prod _{a} ( n Q ( a ) ) ^{n Q (a)}} = 2^{n H (Q)} .

Lower bound. By Stirling's approximation, $m! \leq m^{m} \leq e m \cdot m!$ for $m \geq 1$ . More precisely, $2 π m (m / e)^{m} \leq m! \leq e m (m / e)^{m}$ . Applying to each factorial:

(n Q n) \geq \frac{2 π n ( n / e ) ^{n}}{\prod _{a} e n Q ( a ) ( n Q ( a ) / e ) ^{n Q (a)}} \geq C \cdot \frac{2 ^{n H (Q)}}{( n + 1 ) ^{k}}

where $C$ is a constant absorbed into the $(n + 1)^{k}$ polynomial correction. $□$

Connections Master

37.07.02 — Cramer's theorem is the large-deviation result for empirical means; Sanov's theorem is the stronger result for empirical distributions, and Cramer's theorem follows by contraction.
46.02.01 — The AEP identifies the typical set; the method of types refines this by partitioning sequences into type classes, each of size $2^{n H (Q)}$ .
46.01.02 — KL divergence is both the rate function in Sanov's theorem and the measure of divergence between distributions; this dual role is the central theme.
46.02.03 — Huffman coding achieves entropy for known distributions; universal codes based on types achieve entropy for unknown distributions with vanishing overhead.
46.04.01 — The Stein lemma in hypothesis testing uses Sanov's theorem to identify the optimal error exponent as the KL divergence.

Historical & philosophical context Master

The method of types was developed by Imre Csiszar in a series of papers spanning the 1970s-1990s, culminating in his 1998 survey "The Method of Types" (IEEE Trans. Info. Theory 44(6), pp. 2505-2523). Csiszar's insight was that many results in information theory — Sanov's theorem, universal coding, hypothesis testing — could be derived purely combinatorially by counting type classes, without invoking measure theory or stochastic processes.

Sanov's theorem itself was proved by I. N. Sanov in 1957 ("On the probability of large deviations of random variables," Mat. Sbornik 42, pp. 11-44). The original proof used the change-of-measure technique from large deviations theory. Csiszar's combinatorial proof via the method of types is more elementary and more aligned with the information-theoretic perspective.

The connection between Sanov's theorem and Cramer's theorem (1938) was clarified by the contraction principle in large deviations theory, developed by Varadhan in the 1960s-1970s. The contraction principle shows that Sanov's theorem is the "master" result from which Cramer's theorem follows as a corollary, placing the method of types at the foundation of the large deviations hierarchy.

Bibliography Master

@article{sanov1957,
  author  = {Sanov, I. N.},
  title   = {On the Probability of Large Deviations of Random Variables},
  journal = {Matematicheskii Sbornik},
  volume  = {42},
  pages   = {11--44},
  year    = {1957},
}
@article{csiszar1998,
  author  = {Csisz{\'a}r, I.},
  title   = {The Method of Types},
  journal = {IEEE Transactions on Information Theory},
  volume  = {44},
  number  = {6},
  pages   = {2505--2523},
  year    = {1998},
}
@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},
}

Prerequisites

46.02.01
46.01.02
37.07.02

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §11.1-11.2 (types as histograms, the coin-flip example, why most sequences look typical)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §11.1-11.4 (type classes, size bounds, Sanov's theorem, universal source coding)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §11.1-11.5; Csiszar 1998 The Method of Types IEEE Trans. Info. Theory 44(6) 2505-2523; Dembo & Zeitouni 1998 Large Deviations Techniques and Applications 2e (Springer) §2.1-2.3

References

Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 11.1: definition of types (empirical distributions) and type classes. Theorem 11.1.1: number of types is polynomial in $n$ (at most $(n + 1)^{∣ X ∣ - 1}$ ). Section 11.2: size of type class $(n P n)$ is bounded by $2^{n H (P)}$ to within polynomial factors. Section 11.4: Sanov's theorem — the probability that the empirical distribution falls in a set $E$ of distributions is $\approx 2^{- n i n f_{Q \in E} D (Q ∥ P)}$ . Section 11.5: universal source coding achieves entropy for any stationary source.
Csiszar, I. — The Method of Types · IEEE Transactions on Information Theory 44(6) (1998) 2505-2523. Comprehensive survey of the method of types framework: type classes, conditional types, the I-projection, Sanov's theorem and its applications to hypothesis testing, universal coding, and channel capacity. Sections 2-3 develop the combinatorial properties of types; section 4 proves Sanov's theorem via the method of types.
Dembo, A. & Zeitouni, O. — Large Deviations Techniques and Applications (2nd ed.) · Springer (1998). Section 2.1: the contraction principle and the Gärtner-Ellis theorem for large deviations of empirical means. Section 2.3: Sanov's theorem in the $τ$ -topology — for i.i.d. random variables with distribution $P$ , the empirical distribution satisfies $Pr [T_{X}^{n} \in F] ≐ 2^{- n i n f_{Q \in F} D (Q ∥ P)}$ for closed convex $F$ . The method of types gives a combinatorial proof that avoids the change-of-measure argument.

Estimated time

beginner: 20m
intermediate: 50m
master: 100m