Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 218 / 5 / b

The K-nearest neighbors algorithm takes the majority label among the $k$ training features closest to the query, with a stated tie rule. Its data-dependent risk is the conditional test error given the training sample, and $R_n$ denotes its expectation over that sample.

For one nearest neighbour, condition on a feature value $X=x$ and couple the coincident nearest feature as $X_1=x$. The two labels are conditionally independent Bernoulli$(\eta (x))$, so their mismatch probability isIntegration over $X$ gives