The expected error of 1 nearest Neighbor (1-NN) on large or infinite dataset I have question regarding the expected error of 1NN. Assume the training set is large enough or infinite. let x' is a test point and r be its nearest point. the probability distribution of two classes( 1 and 0) will be essentially the same. Two classes are overlapping totally. The Bayes error rate in this case will be 0.50% (I think). I want to know what is the expected error of 1NN for x' point, is it 1 or 0.50 ?! if Not what is the value.
R(x')=P(Y=1,x')P(Y=0,r)+P(Y=0,x')P(Y=1,r)
R(x')=0.50
I attached figure for the problem.

 A: 1-NN converges to an asymptotic error rate of at most twice the Bayes error rate. It can be less than that, like in this situation, where the Bayes error rate is 50%, and so is the asymptotic error of the classifier. In fact, the result of Cover and Hart (1967), Nearest neighbor pattern classification, is that if the Bayes error rate is $\rho$, then
$$
\rho \le \text{1-NN error} \le 2 \rho (1 - \rho) \le 2 \rho
.$$
If $\rho = 0.5$, then $2 \rho (1 - \rho) = \frac12$
and we see that we have $\frac12 \le \text{1-NN error} \le \frac12$.

In fact, if the Bayes error rate is 50%, then the asymptotic error rate of any classifier is 50%.
It can't be less than 50%, by definition.
Suppose you found a classifier $f(x)$ with a worse error rate, $p > 0.5$. Then think about the classifier that takes what $f(x)$ and then says the opposite, $1 - f(x)$. ("Ask an idiot what they would do, and do the opposite.") This classifier's error rate would be $1 - p$, which is less than the Bayes error of $0.5$, and that's impossible, so finding such an $f$ must be impossible. That is, every classifier has an error rate of 50% when the Bayes error rate is 50%.

Further explanation about error rates here, since it might help to be a little bit formal.
The Bayes error rate refers to a test error rate. That is:


*

*Choose a predictor $f$ mapping input points $x$ to a label $f(x)$, somehow, presumably based on some training data.

*The error rate of $f$ is $\Pr(f(X) \ne Y)$: given a new random test point $X$ with true label $Y$, the probability that $f(X)$ disagrees with $Y$. Importantly, $X$ and $Y$ here are independent of the training data.

*The Bayes error rate is the lowest error rate achievable by any predictor $f$, no matter how it's chosen.


Now, in your case $X$ and $Y$ are independent of each other: $X$ follows some arbitrary distribution, and $Y$ is just equally likely to be $0$ or $1$, i.e. it's Bernoulli$(1/2)$. In this case, for any $f$, regardless of whether it's the 1-NN predictor corresponding to some distribution, a deep neural net, or the predictor that always says $1$, we have that
$$
\Pr(f(X) = Y) = \frac12
$$
as we proved above.
In the particular case of the 1-NN predictor corresponding to some training set:
we get $N$ training examples $(x_i, y_i)$,
and our predictor $f(x)$ returns the $y_i$ corresponding to the closest $x_i$ to $x$.
In the case where both distributions have densities, even as $N \to \infty$, the probability that $X$ is exactly equal to any of the $x_i$ is $0$.
Remember that we're not talking about the training error rate but the test error rate. So, when the two distributions are the same, $f(X)$ will be whatever point happened to be closest, and importantly the true label $Y$ will be totally independent of that because the two distributions are the same: it'll just be uniform. So the error rate when the distributions are the same is 50%, as we proved that it must be.
(Even if they didn't have densities, this would still be true; we just have to define what 1-NN does when there are ties.)
