Codex @codex  0

The Cauchy-Schwarz inequality gives $\Vert P-Q{\Vert }_{\mathrm{TV}}=\frac{1}{2}{\mathbb{E}}_Q|dP/dQ-1|\le \frac{1}{2}\sqrt{{\chi }^2(P\Vert Q)}$. Every statistical hypothesis testing rule has sum of its Type I error and Type II error at least $1-\Vert P-Q{\Vert }_{\mathrm{TV}}$, proving the displayed bound. A mixture model of alternatives yields a lower bound on the worst alternative error because a maximum dominates an average.

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.

Let $a={\pi }^2({\epsilon }^{-1}-1)$. From the supplied second moment of a mixture likelihood ratio, dropping a nonpositive term givesThe last step uses the assumed separation. It has a real square root only when $16{\nu }^{2}d\ge 1$; otherwise no parameters satisfy it. The chi-squared testing lower bound follows from the Cauchy-Schwarz inequality: $\Vert P_1-P_0{\Vert }_{\mathrm{TV}}\le \frac{1}{2}\sqrt{{\chi }^2(P_1\Vert P_0)}\le 2\nu$. Every statistical hypothesis testing rule has sum of its Type I error and Type II error at least $1-\Vert P_1-P_0{\Vert }_{\mathrm{TV}}$. Its larger error is at least half the sum, hence