I'm working on a problem set for a course on Machine Learning and one the problems asks me to prove a given inequality. As an aid for that, the problem gives me the hint to use the following result, which I can understand but I am not able to prove:
Show that $\Sigma_i a_i^2 \geq a_1^2 + \frac{(1-a_1)^2}{C-1}$ for any $C$ real numbers such that $a_1 \geq a_2 \geq … \geq a_C \geq 0$ and $\Sigma_i a_i = 1$
This is speacially useful in the exercise when the $a_i$ are probabilities. However, I could not prove the result. I tried using contradictions and even induction but without any success. Any ideas on how to prove? Thanks a lot in advance!
Best Answer
By Cauchy-Schwarz, $$(1-a_1)^2 = \left( \sum_{j=2}^C a_j\right)^2 \le \sum_{j=2}^C a_j^2 \cdot (C-1)$$