= 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> is
$$
2p_1(x)p_2(x)=2m(x)(1-m(x)).
$$
The assumption gives $c\leq m(x)\leq1/2-c$. Its excess over the conditional Bayes error is
$$
2m(1-m)-m=m(1-2m)\geq2c^2>0.
$$
After taking expectations, the limiting risk remains at least $2c^2$ above the Bayes risk, so one-nearest-neighbour classification is not consistent.
Back to article page
