Prove 1-NN error is at most twice the Bayes error

Cover and Hart (1967). As n -> infinity, the nearest neighbor in metric space converges to a sample from the underlying distribution at x. So the probability 1-NN predicts y = +1 at x converges to P(y=+1 | x) under a tie-breaking convention. The conditional error 1-NN(x) = 2 P(y=+1|x) (1 - P(y=+1|x)). Compare to Bayes error B(x) = min(P, 1-P). Apply pointwise 2P(1-P) <= 2 min(P, 1-P), then take expectation. Equality only in degenerate two-point distributions; in higher dimensions get Cover's tighter bounds with the metric exponent.