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.

  • 7
    $\begingroup$ This follows from the rearrangement inequality: en.wikipedia.org/wiki/Rearrangement_inequality $\endgroup$ – user940 Aug 17 '11 at 14:21
  • 1
    $\begingroup$ 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)$. $\endgroup$ – user940 Aug 17 '11 at 14:40
  • $\begingroup$ @Mike: I changed the tag from probability theory to probability since I think the latter is apt for this question $\endgroup$ – user17762 Aug 17 '11 at 16:19
  • $\begingroup$ @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. $\endgroup$ – Mike Spivey Aug 17 '11 at 17:35
  • $\begingroup$ Are you talking the minimum for fixed value of the pi's and all possible ordering? $\endgroup$ – Marco Disce Feb 18 '16 at 22:36

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.

  • $\begingroup$ @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. $\endgroup$ – Derek O'Connor Aug 17 '11 at 18:35
  • $\begingroup$ Sivaram, thanks for that clear, concise proof. Exactly what I needed. Shame on me for not getting it myself. $\endgroup$ – Derek O'Connor Aug 18 '11 at 13:09
  • 1
    $\begingroup$ @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! $\endgroup$ – user940 Aug 19 '11 at 14:56

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.