# Proving that $f(p)= \sum_{j \neq i}p_ip_j$ is concave

Let $p_i \in [0,1], 1 \leq i \leq n$ so that $p_1+p_2 +...+p_n=1$.

Define $f(p)= \sum_{j \neq i}p_ip_j=1-\sum_{i}p_i^2$. Prove that $f(p)$ is concave.

My effort:

Let $a,b \geq 0, a+b=1$. I try to show that $f(ap+bp') \geq af(p)+bf(p')$.

Then:

$$f(ap+bp')= \sum_{j \neq i}(ap_i+bp'_i)(ap_j+bp'_j) = \sum_{j \neq i}(a^2p_ip_j+b^2p'_ip'_j+abp_ip'_j+abp'_ip_j)$$

$$= a^2f(p)+b^2f(p')+ab\sum_{j \neq i}(p_ip'_j+p'_ip_j)$$

But I don't know where to go from here...

Thanks!

• Did you try to form the second derivative of $f(tp+(1-t)p')$? I haven't tried it myself, so I don't know if it gets you anywhere, but it could be wroth a try. – Harald Hanche-Olsen Jan 11 '14 at 11:01

I think maybe you know this theorem. just for reminding you can use this one: A continuously differentiable function $f:D\subset\mathbb{R^{n}} \rightarrow \mathbb{R}$ is concave if and only if $f(y)- f(x) <= Df(x)(y-x)$ for $x,y\in D$.
i.e. that is , $f(y)- f(x)<=$ $\dfrac{\partial f}{\partial x_{1}}(x)(y_{1}-x_{1})+...+\dfrac{\partial f}{\partial x_{n}}(x)(y_{n}-x_{n})$
Write your function as $$f(p) = \sum_{j \not=i} p_i p_j = (\sum p_i)^2 - \sum p_i^2.$$ Then the gradient vector becomes $$2(\sum_{j\not =1}p_j, \sum_{j\not=2}p_j, \dots, \sum_{j\not=n}p_j)$$ and the Hessian matrix becomes $$2 \begin{pmatrix} 0 & 1 & 1 &\dots 1 \\ 1 & 0 & 1 &\dots 1 \\ \vdots \\ 1 & 1 & 1 \dots 0 \\ \end{pmatrix} = 2H$$ Note that $H$ has one eigenvalue $n-1$ with eigenvector the vector with all component equal to 1, the rest of the eigenvalues is negative. So the function cannot be neither convex nor concave: It has a saddle point. This becomes clear in the case $n=2$ where the function is $f(x,y)=xy$. EDIT sorry, I didnt see your condition that $\sum p_i =1$! That condition annihilates the eigenspace with a positive eigenvalue, so then the function clearly becomes convex. But the expression you give:$f(p) = 1 - \sum p_i^2$, the second term is the negative of a convex function, which gives the result immediately.