= 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> rule
$$
\boxed{\psi=\mathbf1_{\{C>n\varepsilon+a+b\}}.}
$$
The <union bound> and the <Hoeffding inequality> give $P_0(\psi=1)\leq d\exp[-2(a+b)^2/n]\leq\delta$, since $(a+b)^2\geq a^2+b^2$. Conditional on index $j$, accepting the <null hypothesis> implies $c_j\leq n\varepsilon+a+b$. The assumed separation gives $n\pi(1-\varepsilon)>a+2b$, so this threshold lies more than $b$ below the alternative <expected value> $np_1$. The lower-tail <Hoeffding inequality> therefore gives $Q_j(\psi=0)\leq\delta$. Averaging the conditional error over the <mixture model> gives $P_1(\psi=0)\leq\delta$ as well.
Back to article page
