8

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.

Hamou
  • 6,745
Martin Gales
  • 6,878
  • 1
    Might also be worth asking this on stats.SE -- not to suggest it's at all off-topic here, just to increase the number of possible answerers. – walkytalky Oct 25 '10 at 08:08
  • 1
    Do you need an exact answer, or will an approximation do? – Jens Oct 25 '10 at 13:37
  • @Jens: Good question. For large N, Ross gave a nice one solution. – Martin Gales Oct 26 '10 at 06:59
  • @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. – Martin Gales Oct 26 '10 at 07:08
  • 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. – Jens Oct 26 '10 at 07:30

2 Answers2

5

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

Ross Millikan
  • 374,822
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 $

leonbloy
  • 63,430