5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – polkjh
    Jan 4, 2013 at 12:25
  • $\begingroup$ Are you saying that $E[max_{1 \leq i \leq n} X_i]=E[X_i]$ for each $i$? Why? $\endgroup$
    – wedtaur
    Jan 4, 2013 at 14:01
  • 1
    $\begingroup$ @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$. $\endgroup$
    – polkjh
    Jan 4, 2013 at 14:10
  • $\begingroup$ @polkjh Sorry, but follow your idea in counterexample, why $E[X_i]=\frac1m\sum_{j=1}^{n} p_j$ is always true? $\endgroup$
    – wedtaur
    Jan 4, 2013 at 17:57
  • $\begingroup$ 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$ $\endgroup$
    – polkjh
    Jan 5, 2013 at 1:30

1 Answer 1

3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thanks, I need some clarification: when you say $E[max_i X_i]=Prob[X_1=X...$, what concept do you use? $\endgroup$
    – wedtaur
    Jan 4, 2013 at 13:56
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – Ofir
    Jan 4, 2013 at 14:16
  • $\begingroup$ 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? $\endgroup$
    – wedtaur
    Jan 4, 2013 at 18:43
  • 1
    $\begingroup$ @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"}]$.) $\endgroup$
    – Ofir
    Jan 4, 2013 at 18:58
  • $\begingroup$ Perfect! There is a counterexample that prove that simple too? @Ofir $\endgroup$
    – wedtaur
    Jan 4, 2013 at 19:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .