For any region $B_n$ with $P^{\otimes n}(B_n)\geq1-\varepsilon$, let
$$
C_n=\left\{x_1^n:n^{-1}\log\frac{P^{\otimes n}(x_1^n)}{Q^{\otimes n}(x_1^n)}
\leq D(P\Vert Q)+\delta\right\}.
$$
The <weak law of large numbers> gives $P^{\otimes n}(C_n)\to1$, so $P^{\otimes n}(B_n\cap C_n)\geq1-\varepsilon-o(1)$. Therefore
$$
\beta_n\geq Q^{\otimes n}(B_n\cap C_n)
\geq e^{-n(D(P\Vert Q)+\delta)}\{1-\varepsilon-o(1)\}.
$$
Thus $\limsup-n^{-1}\log\beta_n\leq D(P\Vert Q)+\delta$; let $\delta\downarrow0$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 224 / 1 / d / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-224/1/d/solution