3
$\begingroup$

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
    This follows from the rearrangement inequality: http://en.wikipedia.org/wiki/Rearrangement_inequality2011-08-17
  • 1
    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)$.2011-08-17
  • 0
    @Mike: I changed the tag from probability theory to probability since I think the latter is apt for this question2011-08-17
  • 0
    @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.2011-08-17
  • 0
    Are you talking the minimum for fixed value of the pi's and all possible ordering?2016-02-18

1 Answers 1

4

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 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.

  • 0
    @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.2011-08-17
  • 0
    Sivaram, thanks for that clear, concise proof. Exactly what I needed. Shame on me for not getting it myself.2011-08-18
  • 1
    @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!2011-08-19