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

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.