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

Stein's lemma states that for testing $P^{\otimes n}$ against $Q^{\otimes n}$, the smallest Type II error ${\beta }_n$ among tests with Type I error at most any fixed $0<\epsilon <1$ satisfies

The Neyman-Pearson lemma gives an optimal acceptance region for $P$ of the formwith possible boundary randomization. If ${\hat{P}}_n$ is the empirical mass function, thenso equivalently

Fix $\delta >0$ and chooseUnder $P$, the weak law of large numbers makes the normalized log likelihood ratio converge in probability to $D(P\Vert Q)$, so $P^{\otimes n}(B_n({\tau }_n))\to 1$. On this Neyman-Pearson decision region,and henceLetting $\delta \downarrow 0$ proves the direct bound.

For any region $B_n$ with $P^{\otimes n}(B_n)\ge 1-\epsilon$, letThe weak law of large numbers gives $P^{\otimes n}(C_n)\to 1$, so $P^{\otimes n}(B_n\cap C_n)\ge 1-\epsilon -o(1)$. ThereforeThus $\mathrm{limsup}-n^{-1}\log {\beta }_n\le D(P\Vert Q)+\delta$; let $\delta \downarrow 0$.