# Maximum load of a bin in the $n$ balls with weights into $m$ bins problem

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

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

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

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