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

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.