Sanov's theorem

Remarks

For a finite set $\Sigma = \set{1, \dots, m}$, the proof is a counting argument. The probability that $L_n$ equals a given type $\nu$, with $n \nu(i)$ an integer for each $i$, is a multinomial probability. By Stirling's formula, it equals $e^{-n D(\nu \| \mu) + O(\log n)}$, and there are only polynomially many types. The general case reduces to finite partitions of $\Sigma$, or uses Cramér's theorem in a space of measures.

Example: for fair coin tosses, $\mu$ is uniform on $\set{0, 1}$. The event that the fraction of ones is at least $0.6$ has probability $e^{-n c + o(n)}$, where $c = D(\nu \| \mu)$ for $\nu = (0.4, 0.6)$, that is $c = 0.6 \log 1.2 + 0.4 \log 0.8 \approx 0.020$.

Going deeper

For a student

Sanov's theorem gives the Kullback–Leibler divergence a probabilistic meaning and is a basic link between probability and information theory. By the contraction principle, it implies Cramér's theorem for bounded continuous functions of the samples. In statistics it yields error exponents of tests, such as Stein's lemma for hypothesis testing. The conditional limit theorem, or Gibbs conditioning principle, also follows: given a rare constraint on $L_n$, the empirical measure concentrates near the minimiser of $D(\cdot \| \mu)$ under the constraint.