1
$\begingroup$

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!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 23, 2013 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
    Commented Nov 23, 2013 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
    Commented Nov 25, 2013 at 2:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .