Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 210 / 1 / c / Solution

Put $a=\sqrt{n\log d/2}$ and $b=\sqrt{n\log (1/\delta )/2}$. Use the scan statistic $C$ and the statistical hypothesis testing ruleThe union bound and the Hoeffding inequality give $P_0(\psi =1)\le d\exp [-2(a+b{)}^2/n]\le \delta$, since $(a+b{)}^2\ge a^2+b^2$. Conditional on index $j$, accepting the null hypothesis implies $c_j\le n\epsilon +a+b$. The assumed separation gives $n\pi (1-\epsilon )>a+2b$, so this threshold lies more than $b$ below the alternative expected value $n{p}_1$. The lower-tail Hoeffding inequality therefore gives $Q_j(\psi =0)\le \delta$. Averaging the conditional error over the mixture model gives $P_1(\psi =0)\le \delta$ as well.