Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
This follows from the rearrangement inequality: en.wikipedia.org/wiki/Rearrangement_inequality –  Byron Schmuland Aug 17 '11 at 14:21
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)$. –  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
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
@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
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! –  Byron Schmuland Aug 19 '11 at 14:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.