12
$\begingroup$

There are $N$ buckets.

Each second we add one new ball to a random bucket - so at $t=k$, there are a total of $k$ balls collectively in the buckets.

At $t=1$, we expect that at least one bucket contains one ball.

At $t=\sqrt{2N\ln{2}}$, due to birthday paradox, we expect that at least one bucket contains two balls.

.

.

At $t=f(m)$, we expect at least one bucket to contain $m$ balls.

What is the function $f(m)$?

  • 1
    *Someone* wrote a [blog post](http://calculus7.org/2012/01/16/generalized-birthday-problem/) about this.2012-07-16
  • 0
    The birthday paradox is closer to $\sqrt{N\sqrt 2}$. The classic one is $23\approx \sqrt {365 \sqrt 2}$ A naive approach says you have $\frac {N(N-1)}2$ pairs, so when this is of the order of $1$ you should expect a match.2012-08-25
  • 0
    This is called the "balls in bins" problem, and there is huge amount known about it, because it is crucial to understanding the performance of computer hashing algorithms. You might try a web search for "balls in bins" and see what you find out. Or you might enjoy [this](http://ls2-www.cs.uni-dortmund.de/lehre/winter200203/randalg/balls-and-bins.pdf).2012-08-25
  • 0
    This is not $\sqrt{2N\ln(2)}$ to obtain a 50% chance ?2012-08-29
  • 0
    Actually, the probability $p$ that there bucket with more than one ball occurs is first matched or exceeded at $t=\sqrt {2N\ln \frac 1{1-p}}$.2012-08-25

1 Answers 1