Solution

ID: past-exam-of-the-algorithmic-foundations-of-learning-course-of-the-university-of-oxford/2025/3/a/ii/solution

Put with the paper's normalized Hellinger distance. The Hellinger affinity is
The 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 , makes the product calculation immediate. The probability density functions of the product measures factor, and Tonelli's theorem gives
The 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: , and multiplying by the nonnegative gives .

New to topics? Read the docs here!