Convergence of the nearest neighbor rule

If the nearest neighbor rule (NNR) is used to classify unknown samples, then Cover and Hart 1 have shown that the average probability of error using n known samples (denoted by Rₙ) 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 NNR conditioned on the n known samples (denoted by Lₙ. so that ELₙ = Rₙ) 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 Lₙ to R are also given.