Tell me more ×
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.
up vote 9 down vote favorite
2

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)$?

share|improve this question
1  
Someone wrote a blog post about this. – user31373 Jul 16 '12 at 20:03
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}}$. – Roman Chokler Aug 25 '12 at 4:24
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. – Ross Millikan Aug 25 '12 at 4:30
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. – MJD Aug 25 '12 at 4:37
This is not $\sqrt{2N\ln(2)}$ to obtain a 50% chance ? – Xoff Aug 29 '12 at 21:38

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.