6

We have $N$ boxes and $N$ stones. We take a stone, put it into a randomly selected box, proceed to the next stone.

In the end all the stones are in the boxes. Some boxes may be empty, some may contain several stones.

Let $n$ be a maximum number of stones in one box in the end of this experiment.

What's the expected value of $n(N)$?

My intuition says that $n$ must grow with $N$, and computer simulations confirms this, but the growth is much slower than the intuition suggested.

lesnik
  • 2,297
  • From my understanding, to give a few examples, the expected value of the maximum number of stones in one box when $N = 3$ is $2$ and for $N=4$ is $2.4$, and you are looking to generalize this for any positive integer $N$? – WaveX Aug 30 '17 at 18:56
  • @WaveX Hmm. I think n(3) = 17/9. Let's number boxes and stones. Now we have 27 possible outcomes. n = 1 corresponds to 6 outcomes. n = 3 corresponds to 3 outcomes. So n=2 must correspond to 27 - 3 - 6 = 18 outcomes. Expected value of n is (16 + 218 + 3*3)/27 = 17/9, it's a little smaller than 2. – lesnik Aug 30 '17 at 19:10
  • I used a similar method, going back to the $N=3$ example. But I got $18$ possible outcomes by thinking of the ways to add to $3$. We have $$1+1+1$$ $$2+1+0$$ $$3+0+0$$

    Each way has $3!=6$ ways to arrange the stones between the boxes ($1+2+0$ or $1+0+2$ for example) making $18$ ways in total. Then I did the exact same formula as you: $\frac{1}{18} (61 + 62 + 6*3) = 2 $

     – WaveX Aug 30 '17 at 19:20
  • @WaveX I think there are only 3 ways to (3+0+0). They are: put all stones into box 1, or box 2, or box 3. – lesnik Aug 30 '17 at 19:25
  • Yeah, I'm seeing your point now. I didn't take into account that once inside a box then the ordering doesn't matter anymore. It took me to physically start sketching out the possible arrangements. Then what you calculated was the correct formula and correct value for $n(3)$. Sorry for the mix-up :) – WaveX Aug 30 '17 at 19:32

2 Answers2

2

You're looking for the maximum load on putting $n$ balls into $n$ boxes. The Wikipedia article (https://en.wikipedia.org/wiki/Balls_into_bins) gives that with high probability, the maximum load is ${\log n \over \log \log n}(1 + o(1))$, and sources are cited there.

Michael Lugo
  • 22,354
  • Although this is an answer for a slightly different question, this satisfies my curiosity for now! Thanks. – lesnik Aug 30 '17 at 20:58
1

This is a Poisson process and the probability distribution of getting $k$ rocks in any box (where the average $\mu = N/N = 1$) is:

$$P(k) = e^{-\mu} \mu^k/k!$$

The average number in any box is of course $1$.

David G. Stork
  • 29,774