On the Inequality of Cover and Hart in Nearest Neighbor Discrimination

When (X1, ¿1),. . . , (Xn, ¿n) are independent identically distributed random vectors from IRd X 0, 1 distributed as (X, ¿), and when ¿ is estimated by its nearest neighbor estimate ¿ (1), then Cover and Hart have shown that P¿ (1) ¿ ¿n ¿ ¿ ¿ 2E ¿ (X) (1 - ¿ (X) ) ¿ 2R* (1 - R*) where R* is the Bayes probability of error and ¿ (x) = P¿ = 1 | X = x. They have conditions on the distribution of (X, ¿). We give two proofs, one due to Stone and a short original one, of the same result for all distributions of (X, ¿). If ties are carefully taken care of, we also show that P¿ (1) ¿ ¿|X1, ¿1,. . . , Xn, ¿n converges in probability to a constant for all distributions of (X, ¿), thereby strengthening results of Wagner and Fritz.