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.