= Solution
Let $X_1,X_2,\ldots$ be i.i.d. with mass function $Q$ on a finite alphabet, and let $\widehat P_n$ be their <empirical distribution>. <Sanov theorem> states that for every set $\Gamma$ of probability mass functions,
$$
-\inf_{R\in\Gamma^\circ}D_e(R\Vert Q)
\leq\liminf_{n\to\infty}\frac1n\log\mathbb P(\widehat P_n\in\Gamma)
$$
and
$$
\limsup_{n\to\infty}\frac1n\log\mathbb P(\widehat P_n\in\Gamma)
\leq-\inf_{R\in\overline\Gamma}D_e(R\Vert Q),
$$
where interior and closure use the probability-simplex topology. Thus the empirical distributions satisfy a <large deviation principle> with rate function $D_e(\mathord\cdot\Vert Q)$.
Back to article page
