= Solution
Let $X_1,\ldots,X_n$ be IID with full-support mass function $Q$ on a finite alphabet $\mathcal A$, and let the <empirical distribution> be
$$
\widehat P_n(a)=\frac1n\sum_{i=1}^n\mathbf1_{\{X_i=a\}}.
$$
Suppose $E$ is a set of probability mass functions satisfying $E=\overline{E^\circ}$ and that the <information projection> $P^*$ minimizes $D(P\|Q)$ over $E$. Then the limiting <Sanov theorem> is
$$
\lim_{n\to\infty}-\frac1n\log_2Q^n(\widehat P_n\in E)
=D(P^*\|Q).
$$
For each $n$-type $P$, the <method of types> gives
$$
(n+1)^{-|\mathcal A|}2^{-nD(P\|Q)}
\leq Q^n(T_P)\leq2^{-nD(P\|Q)},
$$
and 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^*$ and use the lower type-class bound. Polynomial factors disappear after applying $-n^{-1}\log_2$, and continuity of divergence finishes the proof.
Back to article page
