Suppose there are $m$ balls to be randomly thrown into $n$ bins ($m>n$). Let $X_i$ be the number of balls ending up in bin $i$.

Let $X_{max}$ be the heaviest bin and $X_{min}$ be the lightest bin. In Raab and Steger's paper, the authors state that $$ Pr[X_{max}≥k]≤o(1). $$ However, is there anyway that I can figure out how small $o(1)$ can be? Say, I want the probability to be bounded to some particular value $\frac{1}{n^w}$ ($w≥1$) $$ Pr[X_{max}≥k]≤\frac{1}{n^w}, $$ then, what should k be in order to achieve the bound? (I just cannot figure it out in their paper)

Many thanks for your help!


You can find the answer in this paper by Reviriego, Holst and Maestro. Especially interesting should be formula 23 giving the exact probability distribution. Of course it can be easily seen that your term “heaviest bin” is equivalent to the term “Longest Length Probe Sequence” used in the paper.

  • $\begingroup$ Hi, Waldermar, thank you for your reply, but it seems that in the paper you mentioned, Poisson distribution is used to approximate the final result. Is this a tight bound exactly same as the one in the paper that I mentioned? Could please you give me a brief answer regarding my question? $\endgroup$ – alexander Nov 23 '13 at 8:11
  • $\begingroup$ @alexander The results presented in Table 1 in the paper of P. Reviriego et al. suggest that the Poisson approximation they use is a very precise approximation of the original model. Nevertheless, you can use formula 1 from the paper to get the exact probability distribution for the original model. I’m referring here to exact probabilities (and the title of your post signals that it can be of interest to you) not to the asymptotic results. $\endgroup$ – Waldemar Nov 23 '13 at 20:55
  • $\begingroup$ @Waldermar, I might be too stupid in realizing the close form for formula 1. How can I find it out if I just want to find a tight bound on that probability (instead of exactly solve the recursive formula). Thanks for all of your help! $\endgroup$ – alexander Nov 25 '13 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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