17
$\begingroup$

It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from RANDOM 1998 by Raab and Steger explores this in some detail, showing that as $m$ increases, the probability of going even a little above the expected value of $m/n$ decreased rapidly. Roughly, setting $r = m/n$, they show that the probability of seeing more than $r + \sqrt{r\log n}$ is $o(1)$.

This paper appeared in 1998, and I haven't found anything more recent. Are there new and even more concentrated results along these lines, or are there heuristic/formal reasons to suspect that this is the best one can get ? I should add that a related paper on the multiple-choice variant co-authored by Angelika Steger in 2006 does not cite any more recent work either.

Update: In response to Peter's comment, let me clarify the things I'd like to know. I have two goals here.

  1. Firstly, I need to know which reference to cite, and it does seem like this is the most recent work on this.
  2. Secondly, it is true that the result is quite tight in the r = 1 range. I'm interested in the m >> n range, and specifically in the realm where r might be poly log n, or even n^c. I'm trying to slot this result into a lemma I'm proving, and the specific bound on r controls other parts of the overall algorithm. I think (but am not sure) that the range on r provided by this paper might suffice, but I just wanted to make sure there wasn't a tighter bound (that would yield a better result).
$\endgroup$
  • 3
    $\begingroup$ I learned the name “occupancy problem” from the tag, so thanks for posting an educational question. :) $\endgroup$ – Tsuyoshi Ito Apr 22 '11 at 19:47
  • 7
    $\begingroup$ Looking at the paper of Raab and Steger, it's hard for me to figure out what further results you would want along these lines. Is there a specific question you need to know the answer to? If so, you should ask it, either here or on MathOverflow. In particular, if $r=m/n$, Raab and Steger give a tight bound of $r + \sqrt{2r \log n}$ where $2$ is the correct constant. $\endgroup$ – Peter Shor Apr 23 '11 at 16:05
  • $\begingroup$ @Peter I'll edit the question: it's a valid point. $\endgroup$ – Suresh Venkat Apr 24 '11 at 4:36
8
$\begingroup$

Not really a full answer (nor a useful reference), but just a rather an extended comment. For any given bin, the probability of having exactly $B$ balls in the bin will be given by $p_B = \binom{m}{B} \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$. We can use an inequality due to Sondow, $\binom{(b+1)a}{a}<\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$, to yield $p_B < \left(\frac{(r+1)^{r+1}}{r^r}\right)^B \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$, where $r=\frac{m}{B}-1$. Note that this bound is fairly tight, since a $\binom{(b+1)a}{a}>\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$.

Thus we have $p_B < e^{B(r+1)\ln(r+1) - Br\ln r - m\ln n + (m-B)\ln (n-1)}$. Now, since you are interested in the probability of finding $B$ or more balls in a bin we can consider $p_{\geq B} = \sum_{b=B}^{m} p_b < \sum_{b=B}^{m} e^{b(r+1)\ln(r+1) - br\ln r - m\ln n + (m-b)\ln (n-1)}$. Rearranging the terms, we get $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \sum_{b=0}^{m-B} e^{b(r+1)\ln(r+1) - br\ln r - b\ln (n-1)}.$$

Note the summation above is merely a geometric series, so we can simplify this to give $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)^{m-B+1}}{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)}.$$ If we rewrite $\frac{(r+1)^{r+1}}{r^r (n-1)}$ terms using exponentials, we get $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right)^{m-B+1}}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}},$$ which then becomes $$p_{\geq B} < \frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}}.$$

Now, I take it you care about finding some $B$ such that $p_{\geq B} < \frac{C}{n}$ for some constant $C$, since this gives the total probability of any bin having $B$ or more balls as bounded from above by $C$. This criteria is satisfied by taking $$\frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}} = \frac{C}{n},$$ which can be rewritten as $$B = \frac{\ln\left(\frac{C}{n} e^{m\ln \frac{n}{n-1}} \left(1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right) + e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{(r+1)\ln(r+1) - r\ln r - \ln (n-1)}.$$

I'm not entirely sure how useful this comment will be to you (it's entirely possible I've made a mistake somewhere), but hopefully it can be of some use.

$\endgroup$
  • 1
    $\begingroup$ this is pretty awesome. thanks for the outline. $\endgroup$ – Suresh Venkat Apr 27 '11 at 23:19
  • $\begingroup$ @Suresh: Glad it's useful. $\endgroup$ – Joe Fitzsimons Apr 27 '11 at 23:32

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.