Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 218 / 2

Order the observations so thatusing a fixed or randomized rule for ties. The L-nearest-neighbour classifier estimatesand predicts a class maximizing ${\hat{p}}_k(x)$.

Solved by gpt-5.6-sol high.

Conditional on $X_1,\dots ,X_n$, the $L$ selected class indicators are independent Bernoulli variables. ThereforeandTaking expectations proves the claim.

Solved by gpt-5.6-sol high.

Let $N_{\delta }$ count sample points in the intersection of $[0,1{]}^d$ with the ${\ell }^{\infty }$ ball of radius $\delta$ around $x$. That intersection has volume at least ${\delta }^d$, so $N_{\delta }\sim \mathrm{Bin}(n,q)$ with $q\ge M{\delta }^d$. The event $\Vert X_{(L)}-x{\Vert }_{\infty }>\delta$ implies $N_{\delta }<L$. Since $\mathrm{Var}(N_{\delta })\le nq$ and $nq\ge nM{\delta }^d\ge L$, Chebyshev inequality givesTaking the minimum with the trivial bound one proves the result.

Solved by gpt-5.6-sol high.

Put $R=\Vert X_{(L)}-x{\Vert }_{\infty }$ and ${\delta }_0=(2L/(nM){)}^{1/d}$. If ${\delta }_0\ge 1$, the claim follows from $R\le 1$. Otherwise, for $\delta \ge {\delta }_0$, part (c) givesThe tail-sum formula then yields

Solved by gpt-5.6-sol high.

The Lipschitz continuity of $p_1$ givesPart (d) therefore implies

Solved by gpt-5.6-sol high.

By the Cauchy-Schwarz inequality, part (b), and part (e),This bound tends uniformly to zero ifThe plug-in classifier excess-risk bound then shows that the misclassification risk of the nearest-neighbour classifier converges to the Bayes risk.

Solved by gpt-5.6-sol high.