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:

enter image description here

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:

enter image description here

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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.