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

For two classes, write $m(x)=\min \{p_1(x),p_2(x)\}$, the conditional Bayes error. The nearest-neighbour label and the test label become conditionally independent draws from the same local class distribution, so the limiting conditional error of one-nearest-neighbour classification isThe assumption gives $c\le m(x)\le 1/2-c$. Its excess over the conditional Bayes error isAfter taking expectations, the limiting risk remains at least $2c^2$ above the Bayes risk, so one-nearest-neighbour classification is not consistent.