# Bayes error and nearest neighbor classification

Upon studying for my midterm using Pattern Classification by Richard O. Duda, David G. Stork, Peter E.Hart (2001), I stumbled upon the following exercise:

Using the solutions manual written by David G. Stork, I found myself completely stuck in the very first steps of his proof for (d). He states the following:

What I can't seem to understand is why the sum is over $$n$$ values of $$i$$, while there is a total of $$2n$$ training points ($$n$$ for each category), as well as why the probability in the last line is equal to $$n-1$$, instead of $$2n-1$$, for the same reason.

While scratching my head over this for quite a few days, I realised that this very example is part of a paper by T. Cover and P. Hart, titled Nearest neighbor pattern classification, where the final result is given as

$$P_n(e) = \frac{1}{3} + \frac{1}{\left(n+1\right)\left(n+2\right)}.$$

This very example was also discussed in this thread. On the other hand, D. Stork's solution arrives at

$$P_n(e) = \frac{1}{3} + \frac{1}{(n+1)(n+3)} + \frac{1}{2(n+2)(n+3)}$$

as the final result. So far, I believe that these differences may have something to do with how each author defines $$n$$. Perhaps, one of them denotes the total number of samples by $$n$$, while the other denotes the total number of pairs by $$n$$ (and thus the total number of samples is $$2n$$). Even so, these two results can't be reconciled by taking $$n \to 2n$$.

I would greatly appreciate any thoughts on this.

The main difference between the paper and the exercise is the following: in this exercise, one has to ensure that exactly $$n$$ samples are drawn from $$\omega_1$$ and exactly $$n$$ samples are drawn from $$\omega_2$$. In the paper, each time a sample is to be drawn, a coin is flipped and if it's heads the sample is drawn from $$\omega_1$$ and if it's tails the sample is drawn from $$\omega_2$$. In other words, the paper takes into account configurations where, for example, out of $$n$$ samples, only 1 is drawn from $$\omega_1$$ and $$n-1$$ are drawn from $$\omega_2$$ (even though this configuration corresponds to a small probability).

This means that Stork's solution for the exercise is wrong. On the other hand, what's interesting, is that Stork's solution corresponds to the paper's problem and arrives at a formula that is an exact result,

$$P_n(e) = \frac{1}{3} + \frac{1}{\left(n+1\right)\left(n+3\right)} + \frac{1}{2\left(n+2\right)\left(n+3\right)},$$

in contrast to the paper's solution

$$P_n(e) = \frac{1}{3} + \frac{1}{\left(n+1\right)\left(n+2\right)},$$

which is valid only for $$n=1$$ and large values of $$n$$. This can be seen from a simple Monte Carlo simulation. For $$10^7$$ test runs, the results agree with Stork's formula up to the 4th decimal.

Tl;dr: The exercise's result is neither of the two presented here and the whole exercise requires a completely different approach. However, Stork provided a correct solution to the problem presented in Cover's and Hart's paper, in contrast to the one provided in the paper itself.