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.

$n$ balls, each with a weight $p_i$, are thrown into $m$ bins. Each bin is chosen with uniform probability.

Prove or disprove that the expected value of the maximum load among the loads of bins is $\frac1m\sum_{j=1}^n p_j$, where with "load" means the sum of the weights of the balls in that bin.

Now, I was able to model the problem on the expected value of each bin and this is: $E[X_i]=\frac1m\sum_{j=1}^n p_j$, where $X_i$ is the load of the bin $i$.

Should I calculate something like this: $$E[\max_{1 \leq i \leq n} {X_i}]$$

Do you have any idea? Or is the equation to disprove? But, I have no idea how to have to find a counterexample to disprove with expected values.

share|improve this question
    
The expression you have given is the average load among the bins, so the maximum load is always at least as large as this. Consider the example of 1 ball and 2 bins. –  polkjh Jan 4 '13 at 12:25
    
Are you saying that $E[max_{1 \leq i \leq n} X_i]=E[X_i]$ for each $i$? Why? –  wedtaur Jan 4 '13 at 14:01
1  
@webtaur For each way to assign balls to bins, $\max X_i$ is greater than or equal to average among all bins (which is $\frac{1}{m} \sum _{j=1}^{n} p_i$). And equality occurs here only when all bins get equal load. So $E[max X_i] > \frac{1}{m} \sum _{j=1}^{n} p_i$ (Ofir explains this part in detail in the answer below). You can give an easy counter example too, with n=1, m=2. Maximum load is always $p_1$ here, so its expectation will be $p_1$, but your expression evaluates to $p_1 /2$. –  polkjh Jan 4 '13 at 14:10
    
@polkjh Sorry, but follow your idea in counterexample, why $E[X_i]=\frac1m\sum_{j=1}^{n} p_j$ is always true? –  wedtaur Jan 4 '13 at 17:57
    
I didn't follow your question. Do you want to show that $E[X_i] = \frac{1}{m} \sum _{j=1}^n p_i$? As the bins are chosen with equal probability, we must have $E[X_1] = E[X_2] = \ldots = E[X_m]$. And we know that $\sum_{i=1}^m E[X_i] = E[\sum_{i=1}^m X_i]$. But $\sum_{i=1}^m X_i$ is just the total weight of all balls, which is a constant ($\sum _{j=1}^n p_i$). So $E[X_i] = \frac{1}{m} E[\sum_{i=1}^m X_i] = \frac{1}{m} \sum _{j=1}^n p_i$. You can check this in the example too, for bin $1$, expected value of it's load is, $E[X_1] = (1/2)p_1 + (1/2)*0 = p_1/2$ –  polkjh Jan 5 '13 at 1:30

1 Answer 1

up vote 3 down vote accepted

I want to disprove that $s = \frac1m\sum_{j=1}^n p_j$ is the expected value of the maximum for $m>1$.

(When $m=1$, this is trivially true - all the balls are in the same unique bin.)

But, when $m>1$, this expression is the expected value of the load in any of the bins (use linearity of expectation to see this - each ball has probability $\frac{1}{m}$ to be thrown in a specific bin). So if we let $X_i = \text{load of bin }i$, we have $$\forall i: EX_i = s$$ $$\sum_{i} X_i = \sum_{j} p_j = ms$$

Since $\sum_{i} X_i = ms$, unless $X_i=s$ for each $i$, we have $\max_{i} X_i > s$. So $$E \max_{i} X_i = Pr(X_1 = X_2 = \cdots = X_n=s) s + $$ $$Pr(\text{Not all }X_i \text{ are equal})E(\max_{i} X_i | \text{Not all }X_i\text{ are equal})$$ When $Pr(\text{Not all }X_i \text{ are equal}) > 0$ (true whenever $m>1,n>0$ - for example, you can have the first bin empty and the last full, and vice versa), we have: $$E \max_{i} X_i > ( Pr(X_1 = X_2 = \cdots = X_n=s) + Pr(\text{Not all }X_i \text{ are equal})) s = s$$ since $E(\max_{i} X_i | \text{Not all }X_i\text{ are equal}) > s$.

share|improve this answer
    
Thanks, I need some clarification: when you say $E[max_i X_i]=Prob[X_1=X...$, what concept do you use? –  wedtaur Jan 4 '13 at 13:56
1  
@wedtaur - Law of total expectation (and conditional expectation). I conditioned the expectation on $Y=1_{\text{All }X_i \text{ are equal}}$: $E \max_{i} X_i = E (E \max_{i} X_i | Y)$. –  Ofir Jan 4 '13 at 14:16
    
Ok, I've decomposed: $$ E[max_i X_i]=E[max_iX_i|\text{"All X_i are equal"}]Pr[\text{"All X_i are equal"}]+E[max_iX_i|\text{"Not all X_i are equal"}]Pr[\text{"Not all X_i are equal"}] $$ Next I use the fact of $E[max_i X_i|\text{"Not all X_i are equal"}]>s$ to prove that: $$ E[max_iX_i]>s $$ Am I right? Why that fact is true? Can you give me a counterexample to prove that? –  wedtaur Jan 4 '13 at 18:43
1  
@wedtaur - You're right. Regarding the fact - if the average of some numbers, in our case $X_i$, is $s$, and they are not all equal, it implies their maximum is more than $s$. (In our case, the probability space is finite, so there's some lower bound strictly larger than $s$ for $E[max_iX_i|\text{"Not all X_i are equal"}]$.) –  Ofir Jan 4 '13 at 18:58
    
Perfect! There is a counterexample that prove that simple too? @Ofir –  wedtaur Jan 4 '13 at 19:17

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.