= Solution
The limiting conditional error of one-nearest-neighbour classification is $1-\sum_kp_k(x)^2$. Put $M=\max_kp_k(x)$ and $r=1-M$. By the <Cauchy-Schwarz inequality>, the other $K-1$ probabilities satisfy
$$
\sum_{k:p_k\ne M}p_k^2\geq\frac{r^2}{K-1}.
$$
Consequently
$$
1-\sum_kp_k^2
\leq1-(1-r)^2-\frac{r^2}{K-1}
=2r-\frac K{K-1}r^2.
$$
Now $\mathbb Er=R_{\mathrm{Bayes}}$, and <Jensen inequality> gives $\mathbb Er^2\geq(\mathbb Er)^2$. Taking expectations proves
$$
\lim_{n\to\infty}R(h_n^{\mathrm{1NN}})
\leq2R_{\mathrm{Bayes}}-\frac K{K-1}R_{\mathrm{Bayes}}^2.
$$
Back to article page
