Why $\sum^C_{c\neq c^*}P(c|x)[1-P(c|x)]+p^*(1-p^*) \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]+p^*(1-p^*)?$ I have the following theorem in my textbook:
As the number of samples goes to infinity the error rate of 1-NN is no more than twice the Bayes error rate.
Proof sketch:
Abbreviate notation $P(c|x) := P(Y=c|x)$
The expected (Bayes) error of the Bayes classifier (at x) is $$1-\text{ max }_{c\in\{1,...,C\}}P(c|x)$$
and the expected rate of $1-NN$ (at x) is
$$\sum^C_{c=1}P(c|x_{nn})[1-P(c|x)]$$
observe that as the number of samples goes to infinity, $m\to \infty$,
$$P(c|x)\approx P(c|x_{nn})$$
thus the expected rate of 1-NN (at x) is $$\sum^C_{c=1}P(c|x)[1-P(c|x)]$$
We need to show $$\sum^C_{c=1}P(c|x)[1-P(c|x)]\leq 2[1-\text{ max }_{c\in\{1,...,C\}}P(c|x)]$$:
Let $c^*=\text{ argmax }_{c\in\{1,...,C\}}P(c|x)$ and $p^*=P(c^*|x)$. Observe that $$\sum^C_{c=1}P(c|x)[1-P(c|x)]=\sum^C_{c\neq c^*}P(c|x)[1-P(c|x)]+p^*(1-p^*)\\ \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]+p^*(1-p^*)\\ = (1-p^*)[1-\frac{1-p^*}{C-1}+p^*]$$
Where the second line follows since the sum is maximised when all "$P(c|x)$" have the same value. And since $p^*<1$ we are done.

I don't completely understand how the second line follows. Could someone show me please?


Sorry, quick answer since I'm on my way out the door: you need to think about maximizing the curve
$$
\sum_{c\neq c^*} x_c(1-x_c)\,,\hspace{3em} \text{with } x_c\geq0\,,\hspace{3em}\text{and}\,\, \sum_{c\neq c*} = 1-x_{c^*}\,.
$$
A bit of straightforward calculus (or noticing that $x(1-x)<x$ in the domain) will show you that this is maximized when $x_1=x_2=\ldots=x_{C}$, here when $x_c = (1-x_{c^*})/(C-1)$. So
$$
\sum_{c-c^*} P(c|x)[1-P(c|x)] \leq \sum_{c-c^*} P(c^*|x)[1-P(c^*|x)] = (C-1)P(c^*|x)[1-P(c^*|x)] = (C-1)\left(\frac{1-p^*}{C-1}\right)\left[1-\frac{1-p^*}{C-1}\right]\,.
$$
The result follows.
