Lower bounds for Bayes error estimation

We give a short proof of the following result. Let (X,Y) be any distribution on N x {0, 1}, and let (X-1,Y-1),...,(X-n,Y-n) be an i.i.d. sample drawn from this distribution. In discrimination. the Bayes error L* = inf(g)P{g(X) not equal Y} is crucial importance. Here we show that without further conditions on the distribution of (X,Y), no rate-of-convergence results can be obtained. Let phi(n)(X-1,Y-1,...,X-n,Y-n) be an estimate of the Bayes error, and let {phi(n)(.)} be a sequence of such estimates. For any sequence {a(n)} of positive numbers converging to zero, a distribution of (X,Y) may be found such that E{\L* - phi(n)(X-1,Y-1,...,X-n, Y-n)\} greater than or equal to a(n) infinitely often.