Take the 2-minute tour ×
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.

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

share|improve this question
1  
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
show 7 more comments

1 Answer

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!)

share|improve this answer
    
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
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.