Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 224 / 3

Let $X_1,\dots ,X_n$ be IID with full-support mass function $Q$ on a finite alphabet $\mathcal{A}$, and let the empirical distribution beSuppose $E$ is a set of probability mass functions satisfying $E=\overline{E^{\circ }}$ and that the information projection $P^{\ast }$ minimizes $D(P\Vert Q)$ over $E$. Then the limiting Sanov theorem is

For each $n$-type $P$, the method of types givesand there are at most $(n+1{)}^{|\mathcal{A}|}$ types. Summing the upper bounds over types in $E$ gives the large-deviation upper bound. For the lower bound, choose types $P_n\in E$ converging to an interior distribution arbitrarily close to $P^{\ast }$ and use the lower type-class bound. Polynomial factors disappear after applying $-n^{-1}{\log }_2$, and continuity of divergence finishes the proof.

Define the closed setIt does not contain $Q$. Since the probability simplex is compact, $Q$ has full support, and Kullback-Leibler divergence is continuous and vanishes only at $Q$,The event in the question is exactly $\{{\hat{P}}_n\in E_{ϵ}\}$. The upper-bound half of Sanov theorem gives probability at most a polynomial factor times $2^{-n{c}_{ϵ}}$, which tends to zero. This proves the weak law of large numbers.