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)$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 224 / 2 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-224/2/a/solution