Key points are not available for this paper at this time.
Consider the basic discrimination problem based on a sample of size n drawn from the distribution of (X, Y) on the Borel sets of R d x 0, 1. If 0 ⩽ R*. n → 0 is an arbitrary positive sequence, then for any discrimination rule one can find a distribution for (X, Y), not depending upon n, with Bayes probability of error R* such that the probability of error (R n) of the discrimination rule is larger than R* + ø n for infinitely many n. We give a formal proof of this result, which is a generalization of a result by Cover 1. Furthermore, sup all distributions of (X, Y) with R* = 0 R n ⩾ ½. Thus, any attempt to find a nontrivial distribution-free upper bound for R n will fail, and any results on the rate of convergence of R n to R* must use assumptions about the distribution of (X, Y).
Luc Devroye (Mon,) studied this question.