# Minimize Expected Value

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.

-
This follows from the rearrangement inequality: en.wikipedia.org/wiki/Rearrangement_inequality –  Byron Schmuland Aug 17 '11 at 14:21
You could also prove it using the expression for the expected value as the sum of tail probabilities: $E(X)=\sum_{k=0}^n P(X>k)$. –  Byron Schmuland Aug 17 '11 at 14:40
@Mike: I changed the tag from probability theory to probability since I think the latter is apt for this question –  user17762 Aug 17 '11 at 16:19
@Sivaram: I do think probability-theory is more apt, since the question is about proving a statement about probability rather than calculating a probability, but I don't feel strongly enough about it to engage in a tag war over it. :) The boundary between the probability-theory and probability tags is rather vague, anyway. –  Mike Spivey Aug 17 '11 at 17:35

## 1 Answer

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.

-
@Byron: Thanks for that link. I had never heard of the Rearrangement Inequality but suspected there was something similar, but could never find it since I first came ipon this problem many years ago when analysing a discrete random number generator. –  Derek O'Connor Aug 17 '11 at 18:35
Sivaram, thanks for that clear, concise proof. Exactly what I needed. Shame on me for not getting it myself. –  Derek O'Connor Aug 18 '11 at 13:09
@Derek There is no shame in asking "dumb" questions. I have done the same thing myself on this site. We all have things to learn, and the community here loves to help out! –  Byron Schmuland Aug 19 '11 at 14:56