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.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 218 / 3 / d / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-218/3/d/solution