Exercise 9.5

We compute the distances between $x_1,x_2$ with $x_{\mathit{test}}$, we have

Suppose there are $k$ $+1$s in $a_i$ and $l$ $+1$s in $b_i$, then we have

To correctly classify $x_{\mathit{test}}$ we want to have $d_1<d_2$, which indicates that $k<l+1$, i.e. $k\le l$.

So we need compute the probabilities of the number of $+1$ in $a$ is less than or equal to the number of $+1$s in $b$. Both $a$ and $b$ have $d$ elements, by symmetry the probability of $P(k>l)=P(l<k)$, i.e. the probability of $a$ having more $+1$ than $b$ is equal to the probability of $a$ having less $+1$ than $b$. So we have

, thus $P(k\le l)=P(k<l)+P(k=l)=\frac{1}{2}(1+P(k=l)).$$$

We only have to solve the probability $P(k=l)$.

For a given $k$, the probability of

So we have

So

This is the probability of classifying $x_{\mathit{test}}$ correctly with two data points.

If there’s a third data point $x_3$, then to correctly classify the $x_{\mathit{test}}$, we need have both $d_1<d_2$ and $d_1<d_3$, so the probability

The probability of correctly classifying the $x_{\mathit{test}}$ drop about half.