= Solution
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 is
$$
2\eta(x)\{1-\eta(x)\}
\leq2\min\{\eta(x),1-\eta(x)\}.
$$
Integration over $X$ gives
$$
R_n(\psi^{1\mathrm{NN}})\leq2R(\psi^{\mathrm{Bayes}}).
$$
Back to article page
