8
$\begingroup$

Consider the scheme of random placing balls into $N=1000$ cells. We continue the procedure of placing balls as long as a last cell remains empty. The process terminates when a ball is placed into this cell. At this moment several cells (or a certain cell) contain(s) a maximum number of balls among all cells. What is the expectation of this maximum?

As an application of this scheme consider $N$ people who enter a lottery game. Each raffle is equivalent to the random placing of a ball into $N$ cells. We take a look at this process as long as each person has won at least once.

  • 0
    Might also be worth asking this on [stats.SE](http://stats.stackexchange.com/) -- not to suggest it's at all off-topic here, just to increase the number of possible answerers.2010-10-25
  • 0
    Do you need an exact answer, or will an approximation do?2010-10-25
  • 0
    @Jens: Good question. For large N, Ross gave a nice one solution.2010-10-26
  • 0
    @Jens: But in case of moderate N, do you think that an exact solution exists? For N=1000 it was quite surprising that the maximum is so small.2010-10-26
  • 0
    No, I don't think so. In Ross' approach, once you know what number $N$ of balls have been used, you are faced with the problem of distributing them between the cells, or, equivalently, finding the partitions of $N$ with 1000 terms, one of which must be 1. In my past experience, every problem that could be reduced to number partitioning was ugly. =) That does not mean that there is no better approach, though.2010-10-26

2 Answers 2

4

You can get an approximate answer. The coupon collector's problem tells you that the expected number of balls is $n*H_n$ or about 7485 for n=1000. So the average bin will have 7.485 balls. If you look at the Poisson distribution for 7.485 and find the number where it falls to 1/1000. I make that 17 or 18. The motivation is that you have 999 bins with an average occupancy of 7.485. The highest will be at a probability of about 1/999

  • 0
    What is the intuition behind the last step?2010-10-25
  • 0
    This is an excellent answer! Thanks!2010-10-26
0

To refine Ross' answer(+1), at the moment when the last (say, 7400) ball fills the last cell, the distribution of the remaining cells should approach that of 999 iid ZERO-TRUNCATED Poisson variables with media u=7399/999.

Updated: With media = 7.484, this gives $\lambda \approx 7.480 $