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

The conditional class probability is $p_k(x)=\mathbb{P}(Y=k\mid X=x)$. A Bayes classifier choosesand its Bayes risk isA sequence of classifiers is consistent when $R(h_n)\to R_{\mathrm{Bayes}}$ as $n\to \infty$, with convergence interpreted in probability or in expectation according to whether the training sample is conditioned upon.

The $L$-nearest-neighbour classifier finds the $L$ training predictors nearest to $x$ and returns the majority class among their labels. Increasing $L$ averages more labels and reduces variance of an estimator, but uses observations farther from $x$ and therefore increases bias of an estimator; decreasing $L$ reverses this bias-variance tradeoff.

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.

The limiting conditional error of one-nearest-neighbour classification is $1-{\sum }_k{p}_k(x{)}^2$. Put $M={\max }_k{p}_k(x)$ and $r=1-M$. By the Cauchy-Schwarz inequality, the other $K-1$ probabilities satisfyConsequentlyNow $\mathbb{E}r=R_{\mathrm{Bayes}}$, and Jensen inequality gives $\mathbb{E}{r}^2\ge (\mathbb{E}r{)}^2$. Taking expectations proves