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!


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)$$

  • $\begingroup$ Thanks for your answer! I think this solves the problem. $\endgroup$ – Raul Guarini Nov 20 '18 at 12:26

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.