Minimize Expected Value

Question

Can anyone prove, or disprove with a counter-example, the following statement:

The value of $\sum_{k=1}^n kp_k$ with $\sum_{k=1}^np_k = 1,\,$ is minimized if $p_1 \ge p_2 \ge \cdots \ge p_n$, and maximized if $p_1 \le p_2 \le \cdots \le p_n$

This problem arises in the analysis of an algorithm to generate values from a discrete random variable, using the inverse transform method.

I can prove it for $n = 2$, but cannot get any further. Hardy, Littlewood, and Polya's, Inequalites, is beyond me. I have tested the statement empirically in Matlab and it seems to be true.

I have the awful feeling that this is a well-known result, but I'm not a mathematician and don't know how to find or prove the statement.

Answer 1

Lets start with the minimization problem i.e. Minimize $\sum_{k=1}^{n} k p_k$ with $\sum_{k=1}^{n} p_k = 1$ and $p_k \geq 0$. Consider $p_i$ and $p_j$ and assume $i < j$. At the minimum, if $p_i$ were to be less than $p_j$, we can swap $p_i$ and $p_j$ to get a lower sum since if $i<j$ and $p_i < p_j$, then $i p_j + j p_i < i p_i + j p_j$. Contradicting the fact that it is the minimum. Argue on similar means for the maximization problem as well.