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?


Let's define  $y_c:=P(c|x)$, $\forall{c} \in \{1,2,\ldots, C\}$, then we have $y_{c^{*}}=p^{*}$
Also, let $f\left(y_1,y_2,\ldots,y_{c^{*}-1},y_{c^{*}+1},\ldots,y_C\right)=\sum\limits_{c\neq c^{*}}y_c(1-y_c)$, this is the function we want to maximize (note the absence of $c^{*}$ in the variables).
Also, we have a constraint that $\sum\limits_{c=1}^{C}y_c=1$, since the posterior probabilities must sum to $1$.
Let's define the constraint function $g\left(y_1,y_2,\ldots,y_{c^{*}-1},y_{c^{*}+1},\ldots,y_C\right)=\sum\limits_{c\neq c^{*}}y_c + p^{*}-1=0$,
s.t. we have to maximize $f$ w.r.t. the constraint $g$.
It means we must have $\nabla f = \lambda \nabla g$ for some $\lambda$, when $f$ is an extremum (using the Lagrange multiplier).
$\implies \begin{align}
    \begin{bmatrix}
           1-2y_1 \\
           1-2y_2 \\
           \vdots \\
           1-2y_{c^{*}-1} \\
           1-2y_{c^{*}+1} \\
           \vdots \\
           1-2y_{C} 
         \end{bmatrix}
    \end{align}$ $=\lambda 
    \begin{align}
    \begin{bmatrix}
           1 \\
           1 \\
           \vdots \\
           1 \\
           1 \\
           \vdots \\
           1 
         \end{bmatrix}
        \end{align}$
$\implies y_c = \dfrac{\lambda-1}{2}$, $\forall{c} \neq c^{*}$
Also, we must have the constraint satisfied, i.e.,
$\sum\limits_{c\neq c^{*}}y_c + p^{*}-1=\sum\limits_{c\neq c^{*}}\dfrac{\lambda-1}{2}+p^{*}-1= 0$
$\implies (C-1)\dfrac{\lambda-1}{2}+p^{*}-1= 0$
$\implies y_c=\dfrac{\lambda-1}{2}=\dfrac{1-p^{*}}{C-1}$, $\forall{c} \neq c^{*}$
Hence, at maximum, we have,
$f_{max}\left(y_1,y_2,\ldots,y_{c^{*}-1},y_{c^{*}+1},\ldots,y_C\right)=\sum\limits_{c\neq c^{*}}y_c(1-y_c)=\sum\limits_{c\neq c^{*}}\dfrac{1-p^{*}}{C-1}\left(1-\dfrac{1-p^{*}}{C-1}\right)$
$=(C-1).\dfrac{1-p^{*}}{C-1}\left(1-\dfrac{1-p^{*}}{C-1}\right)$
Now, since we have $f \leq f_{max}$,
$\implies \sum\limits^C_{c\neq c^*}P(c|x)[1-P(c|x)] \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]$
$\implies \sum\limits^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^*)$
