Bayes error and nearest neighbor classification

Question

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.

Answer 1

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.