A real valued function $f$ defined on an interval is called concave, if for any two points $a$ and $b$ in that interval, $$ f(ta+(1-t)b)\geq tf(a)+(1-t)f(b)\quad\forall\quad t\in[0,1] $$


A line connecting the points on the concave function lies below or on the function.

This is fine.

But can we extend that to more than two points ?, i.e.,

$$ f(\sum_{i=1}^n p_ia_i)\geq \sum_{i=1}^np_if(a_i)\quad\forall\quad p_i,a_i\in[0,1] $$ where $\sum_ip_i=1$

My Attempt

Assuming that it is true for $n$ points, i.e., $f(\sum_{i=1}^n p_ia_i)\geq \sum_{i=1}^np_if(a_i)\quad\forall\quad p_i,a_i\in[0,1]$

For $n+1$ points we have

\begin{align} \sum_{i=1}^np_if(a_i)&=p_1f(a_1)+p_2f(a_2)+\cdots+p_nf(a_n)+p_{n+1}f(a_{n+1})\\ &=p_1f(a_1)+p_2f(a_2)+\cdots+(p_n+p_{n+1})f(a_n)-p_{n+1}f(a_n)+p_{n+1}f(a_{n+1})\\ &\leq f(p_1a_1+p_2a_2+\cdots+(p_n+p_{n+1})a_n)-p_{n+1}f(a_n)+p_{n+1}f(a_{n+1})\\ &\leq f(p_1a_1+p_2a_2+\cdots+(p_n+p_{n+1})a_n)+p_{n+1}f(a_{n+1}) \end{align}

\begin{align} f(\sum_{i=1}^{n+1} p_ia_i)&=f(p_1a_1+p_2a_2+\cdots+p_na_n+p_{n+1}a_{n+1})\\ &=f(p_1a_1+p_2a_2+\cdots+(p_n+p_{n+1})a_n-p_{n+1}a_n+p_{n+1}a_{n+1}) \end{align}

How do I proceed further to finish the proof ?, Is there a better method than induction to approach this ?


1 Answer 1


This could be done by just expanding the term $f(\sum p_i a_i)$:

$$ f(\sum_{i=1}^n p_i a_i) = f(p_1a_1 + \sum_{i=2}^n p_i a_i) \\ = f(p_1a_1 + (1-p_1)\sum_{i=2}^n \frac{p_i}{1-p_1} a_i) \\ \geq p_1f(a_1) + (1-p_1)f(\sum_{i=2}^n \frac{p_i}{1-p_1} a_i) \\ = p_1f(a_1) + (1-p_1)f\left( \frac{p_2}{1-p_1} a_2 + (1-\frac{p_2}{1-p_1}) \sum_{i=3}^n \frac{1}{1-\frac{p_2}{1-p_1}}\frac{p_i}{1-p_1} a_i \right) \\ = p_1f(a_1) + (1-p_1)f\left(\frac{p_2}{1-p_1}a_2 + \frac{1-p_1-p_2}{1-p_1}\sum_{i=3}^n \frac{p_i}{1-p_1-p_2}a_i\right) \\ \geq p_1f(a_1) + (1-p_1)\left( \frac{p_2}{1-p_1}f(a_2) +\frac{1-p_1-p_2}{1-p_1}f(\sum_{i=3}^n\frac{p_i}{1-p_1-p_2}a_i) \right) \\ =p_1f(a_1) + p_2f(a_2)+(1-p_1-p_2)f(\sum_{i=3}^n\frac{p_i}{1-p_1-p_2}a_i)\\ =... \\ =p_1f(a_1) + p_2f(a_2) +...+ p_{n-1}f(a_{n-1}) + (1-p_1-...-p_{n-1})f(\sum_{i=n}^n \frac{p_i}{1-p_1-...-p_{n-1}}a_i)\\ = p_1f(a_1) + p_2f(a_2) + ... + p_nf(a_n) $$

Hope this could help you.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .