The factor of two
If \tau_1(x)=0.9 at a point, find the conditional Bayes error and the asymptotic nearest-neighbour error. Compare the multiplier 1+\sqrt{2/k} for k=1, 7, and 50.
Worked answer (click to show)
The conditional Bayes error is r=\min(0.9,0.1)=0.1. The asymptotic nearest-neighbour error is
2\tau(1-\tau)=2(0.9)(0.1)=0.18,
which is 1.8 times the Bayes error and below the factor-two bound. The multiplier 1+\sqrt{2/k} is 2.41 for k=1, 1.53 for k=7, and 1.20 for k=50. For k=1 the sharper Cover–Hart bound 2R^*(1-R^*) is tighter than 1+\sqrt{2}. This is a large-sample comparison for the stated nearest-neighbour setting. Bayes consistency of a sequence k_n requires conditions such as k_n\to\infty and k_n/n\to 0. Increasing k to the full sample size is not that regime.