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.

If I have $m$ distinct boxes, and $n$ distinct balls. I put all of these balls into the boxes with one box possibly containing more than one balls. What is the expected maximum number of balls in one box?

Appreciate your thoughts on solving this problem.

share|improve this question
    
@Yuval: how to deal with max? Can you please give more details? –  Qiang Li Feb 13 '11 at 3:53
    
Your balls and boxes should be non-distinguishable, since you do not care which box has the highest number of balls, and "which" balls you count does not matter. –  milcak Feb 13 '11 at 3:55
    
@milcak: what do you mean by "should"? In my case, I just want them to be distinguishable? If you like, you can also please give the non-distinguishable solution. –  Qiang Li Feb 13 '11 at 4:12
    
@Qiang Li what I meant is that the solution to both answers will be the same, so the way you phrased it can confuse someone. Say you distinguish the balls by color. Then in any arrangement you have some box that has some number of balls. But see that the number of balls does not depend on the color of the balls! You count all of them. Same for boxes you don't care which box has the most, you do not distinguish. –  milcak Feb 13 '11 at 4:22
1  
@milcak: Yes, the two would yield different results, and in order to get the expectation Yuval described, you'd need to count that as $1$ of the $m^n$ elementary events, namely the one where for each ball you chose to put it in that one box. It doesn't matter in which order you go through the balls and decide where to put them; what matters is only where you put each ball. –  joriki Feb 13 '11 at 8:04

1 Answer 1

up vote 4 down vote accepted

This is answered in a paper by Raab and Steger (they switch your $n$ and $m$). The case $n=m$ is simpler and had been known before (see their introduction).

Intuitively, in order to find the "correct" answer, you calculate the expected number of bins $X_t$ which get at least $t$ balls; the value of $t$ such that $X_t \approx 1$ should be "close" to the expectation.

In order to make this rigorous, follow these steps:

  1. Find a critical value $t_0$ such that if $t \ll t_0$ then the probability that a given box gets at least $t$ balls is very close to $1$, and if $t \gg t_0$ then it is very close to $0$.
  2. When $t \gg t_0$, a union bound shows that with high probability no box gets at least $t$ balls.
  3. When $t \ll t_0$, the expected number of boxes with at least $t$ balls is very close to $m$, and so the probability that no box gets at least $t$ balls is very small.
  4. Deduce that most of the probability mass of the expectation is concentrated around $t_0$, and so the expectation itself is close to $t_0$.

When doing the calculations, we hit a problem in step 3: the number of expected boxes with at least $t$ balls is not $m$ but somewhat smaller. Raab and Steger show that the variable $X_t$ is concentrated around its expectation (using the "second moment method", i.e. Chebyshev's inequality), and so $\Pr[X_t = 0]$ is indeed small.

Most of the work is estimating the binomial distribution of the number of balls in each box, finding the correct $t_0$ for each case; the method fails when the number of balls is significantly smaller than the number of bins.


Here is some Sage code:

def analyze_partition(partition, bins):
    last = partition[0]
    counts = [1]
    for part in partition[1:]:
        if part != last:
            last = part
            counts += [1]
        else:
            counts[-1] += 1
    counts.append(bins - sum(counts))
    return multinomial(*partition) * multinomial(*counts)

def expected_max(balls, bins):
    return sum([max(partition) * analyze_partition(partition, bins)
                for partition in partitions(balls)
                if len(partition) <= bins])/bins^balls

When plugging $10$ balls and $5$ bins, I get $$1467026/390625 \approx 3.76.$$

share|improve this answer
    
The question is treated and the answer is bounded, but the question isn't answered :-) –  joriki Feb 13 '11 at 9:48
    
@Yuval: I would agree with joriki. What if in case i need an exact solution, rather than bounds, or even high probability bounds? –  Qiang Li Feb 13 '11 at 17:43
    
@Qiang: It is very easy to give an exact formula for the expectation, using the definition of expectation and multinomial coefficients. However, this formula doesn't help you estimate the expectation. –  Yuval Filmus Feb 13 '11 at 18:14
    
There are many functions which are easy to estimate but hard to evaluate exactly, for example the prime-counting function $\pi$ and the partition function $p$. In these cases, however, there are non-trivial algorithms to calculate the functions explicitly. –  Yuval Filmus Feb 13 '11 at 18:15
    
I therefore suggest you rephrase your questions as: What is the most efficient algorithm for computing said expectation exactly? –  Yuval Filmus Feb 13 '11 at 18:16

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.