On the inequality of cover and hart in nearest neighbor discrimination
L Devroye
IEEE Transactions on Pattern Analysis and Machine Intelligence 1981, 3 (1): 75-8
21868920
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.
Full Text Links
Find Full Text Links for this Article
You are not logged in. Sign Up or Log In to join the discussion.