Past exam of the algorithmic foundations of learning course of the University of Oxford / 2025 / 3 / a

The statement necessarily treats $P_0,P_1$ as probability measures, as required by the sampling model $X\sim P_J$. The word "measures" in the introduction must be read with this normalization. Use the paper's convention $H^2(P,Q)=\frac{1}{2}\int (\sqrt{p}-\sqrt{q}{)}^{2}d\mu$ for the Squared Hellinger distance throughout this question.

A measurable binary hypothesis test $\psi$ is determined by the measurable set $A=\{x:\psi (x)=1\}$. Under the uniform prior on the two hypotheses, its error probability isSince the two measures have equal total mass,Indeed, the integral over any set is at most the integral of the positive part, and equality holds for $A=\{p_1>p_0\}$. This is also the total variation distance. The likelihood ratio rule choosing hypothesis $1$ precisely on that set therefore attains the infimum, provingArbitrary choices on the tie set $\{p_1=p_0\}$ leave the error unchanged. This is the exact link between total variation distance and optimal binary statistical hypothesis testing.

Put $h=H^2(P_0,P_1)$ with the paper's normalized Hellinger distance. The Hellinger affinity isThe last bound follows from the Cauchy-Schwarz inequality and the unit integrals of the two probability density functions. Using a common dominating probability measure, for example $(P_0+P_1)/2$, makes the product calculation immediate. The probability density functions of the product measures factor, and Tonelli's theorem givesThe Squared Hellinger distance is independent of the choice of common dominating measure, so this calculation applies to the original distributions. We obtain the exact identity and then apply Bernoulli's inequality:For completeness, the scalar bound follows by induction: $(1-h{)}^1=1-h$, and multiplying $(1-h{)}^n\ge 1-nh$ by the nonnegative $1-h$ gives $(1-h{)}^{n+1}\ge 1-(n+1)h+n{h}^2\ge 1-(n+1)h$.