# Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$?

That is, consider the following random process. At each of times $t=1, 2, 3, \dots$,

• Pick up a ball (from some infinite supply of balls that you have).
• Assign it to one of $b$ buckets, uniformly at random, and independent of choices made for previous balls.

For this random process, let $T = T(s,b)$ be the time such that

• At time $T-1$ (after the $T-1$th ball was assigned), for each bucket, the number of balls assigned to it was $\le s$.
• At time $T$ (after the $T$th ball was assigned), there is some bucket for which the number of balls assigned to it is $s + 1$.

What can we say about $T$? If we can get the distribution of $T(s,b)$ that would be great, else even knowing its expected value and variance, or even just expected value, would be good.

Beyond the obvious fact that $T \le bs+1$ (and therefore $E[T]$ exists), I don't see anything very helpful. The motivation comes from a real-life computer application involving hashing (the numbers of interest are something like $b = 10000$ and $s = 64$).

-
This problem has been extensively studied. See e.g. Theorem 1 in the paper “'Balls into Bins' — A Simple and Tight Analysis” by Martin Raab and Angelika Steger [available online: www14.informatik.tu-muenchen.de/personen/raab/publ/balls.pdf]. –  Yury Jul 15 '12 at 17:15
@Yury: Thanks for the reference. But I forgot to mention that I did encounter this same (I think) paper while doing a Google search, but it is not very useful to me because it gives only asymptotic bounds: it's not very helpful to know that some probability is $o(1)$; I am more interested (given the practical motivation) in calculating the actual value, for numbers like the 10000 buckets of size 64 I mentioned. (Also, I think it is not trivial to go from the form given in Theorem 1 to a distribution of $T$, is it? Even if its probability $\Pr[M > k]$ was known as an actual value.) –  ShreevatsaR Jul 15 '12 at 17:20
BTW: I would imagine this has been extensively studied; I am just surprised I am unable to find anything. I don't necessarily need a closed form; some efficient method of calculating this number would be good too. –  ShreevatsaR Jul 15 '12 at 17:22
Roughly speaking, if $T \gg n$, we can assume that the number of balls in each bin is a Gaussian r.v. with expectation $T/b$ and standard deviation $\sqrt{N b (1 - 1/b)}$; r.v. for different bins are “almost” independent. Then the number of balls in the heaviest bin is approximately $T/b + \sqrt{N b (1 - 1/b)} \cdot q_n$, where $q_n$ is such that $Pr[\gamma > q_n] = 1/n$ (here, $\gamma$ is a standard normal variable). –  Yury Jul 15 '12 at 17:22
The little $o(1)$ term in Theorem 1 is really small. For practical purposes, it is 0. –  Yury Jul 15 '12 at 17:25

I just wrote some code to find the rough answer (for my particular numbers) by simulation.

\$ gcc -lm balls-bins.c -o balls-bins && ./balls-bins 10000 64
...
Mean: 384815.56 Standard deviation: 16893.75 (after 25000 trials)


This (384xxx) is within 2% of the number ~377xxx, specifically

$$T \approx b \left( (s + \log b) \pm \sqrt{(s + \log b)^2 - s^2} \right)$$

that comes from the asymptotic results (see comments on the question), and I must say I am pleasantly surprised.

I plan to edit this answer later to summarise the result from the paper, unless someone gets to it first. (Feel free!)

-
Just leaving a comment here in case the one on the question disappears: www14.informatik.tu-muenchen.de/personen/raab/publ/balls.pdf –  ShreevatsaR Dec 6 '13 at 10:08
("Balls into Bins": A Simple and Tight Analysis) by Martin Raab and Angelika Steger –  ShreevatsaR Dec 6 '13 at 10:14
p. 116 of Analytic Combinatorics has exact expression, and some history. –  ShreevatsaR Dec 13 '13 at 17:38