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

For each ball, the event of landing in $S_j$ is a Bernoulli distribution trial. Under the null hypothesis its probability is $\epsilon$. Under the selected alternative $Q_j$, its probability is $p_1=\pi +(1-\pi )\epsilon =\epsilon +\pi (1-\epsilon )$. The placements are independent random variables conditional on that selected index, so the count has the binomial distribution:The second assertion concerns $Q_j$, rather than the unconditional mixture model $P_1$.

The Hoeffding lemma for a Bernoulli distribution variable gives $\mathbb{E}{e}^{s(B-p)}\le e^{s^2/8}$. Multiplication of the moment-generating functions of the independent random variables gives $\mathbb{E}{e}^{s(X-np)}\le e^{n{s}^2/8}$. Thus the centered count is a sub-Gaussian random variable with variance proxy $n/4$. The Chernoff bound, optimized at $s=4t/n$, givesThe same estimate holds for the lower tail by applying the Chernoff bound to $-(X-np)$. No independence between different bin counts is needed.

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.

For $P\ll Q$, the chi-squared divergence is ${\chi }^2(P\Vert Q)={\mathbb{E}}_Q[(dP/dQ-1{)}^2]$. Write $L_j=d{Q}_j/d{P}_0$ for the likelihood ratios of the complete $n$-ball sample. Since $d{P}_1/d{P}_0=d^{-1}{\sum }_j{L}_j$ and ${\mathbb{E}}_0{L}_j=1$, the second moment of a mixture likelihood ratio givesIf instead $L_j$ denotes a one-ball likelihood ratio, its cross moment must be raised to the $n$th power for the full sample, by independence.

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