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
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.

Trending Papers

Remove bar
Read by QxMD icon Read

Save your favorite articles in one place with a free QxMD account.


Search Tips

Use Boolean operators: AND/OR

diabetic AND foot
diabetes OR diabetic

Exclude a word using the 'minus' sign

Virchow -triad

Use Parentheses

water AND (cup OR glass)

Add an asterisk (*) at end of a word to include word stems

Neuro* will search for Neurology, Neuroscientist, Neurological, and so on

Use quotes to search for an exact phrase

"primary prevention of cancer"
(heart or cardiac or cardio*) AND arrest -"American Heart Association"