Convergence of the nearest neighbor rule

If the nearest neighbor rule is used to classify unknown samples then Cover and Hart have shown that the average probability of error using n known samples (denoted by Rn)converges to a number R as n tends to infinity where R∗ ≤ R ≤ 2R∗ (1-R∗) and R∗ is the Bayes probability of error. Here it is shown that when the samples lie in n-dimensional Euclidean space, the probability of error for the nearest nearest neighbor rule conditioned on the n known samples (denoted by Ln so that ELn = Rn) converges to R with probability 1 for mild continuity and moment assumptions on the class densities. Two estimates of R from the n known samples are shown to be consistent. Rates of convergence of Ln to R are also given.