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

Stein's lemma states that for distinct probability mass functions $P,Q$ on a finite alphabet, the best exponential decay rate of the Type II error ${\beta }_n=Q^{\otimes n}(B_n)$ among tests whose Type I error ${\alpha }_n=P^{\otimes n}(B_n^c)$ is eventually at most any fixed $ϵ\in (0,1)$ is

For the direct part, define the information-density typical regionThe weak law of large numbers under $P$ gives ${\alpha }_n\to 0$, while

For the converse, letAgain $P^{\otimes n}(C_n)\to 1$. Any test with $P^{\otimes n}(B_n)\ge 1-ϵ$ satisfiesOn $C_n$, $Q^{\otimes n}\ge 2^{-n(D+\delta )}{P}^{\otimes n}$, henceThus ${\mathrm{limsup}}_n-n^{-1}{\log }_2{\beta }_n\le D+\delta$. Letting $\delta \downarrow 0$ proves optimality.

Using the paper's full-${\ell }^1$ convention, the total variation distance isLet $A_{+}=\{a:P(a)\ge Q(a)\}$. Since the signed differences sum to zero,For every $B\subseteq A$, its positive difference is at most the sum over $A_{+}$, and its negative difference has the same bound by taking the complement. Therefore

Let $B_n$ be the region on which the test chooses $P_n$. ThenMinimizing over decision regions is therefore equivalent to maximizing the signed difference. Part b givesThe minimizing region is $\{x:P_n(x)\ge Q_n(x)\}$, the equal-prior Neyman-Pearson decision region.