Balls and Bins analysis in the m >> n regime

Question

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

Answer 1

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.

Answer 2

For all $m\ge n$,the bound is tight up to a factor of $\sqrt{10}$ in the additive term, in the following sense:

Lemma 1. The probability that all bins have fewer than $m/n + \sqrt{\frac{m}{10n}\ln n}$ balls is at most $\exp(-n^{1/10})$.

Proof. The starting point is the tightness of the Chernoff bound. Specifically, Lemma 4 of https://doi.org/10.1137/12087222X (and https://cstheory.stackexchange.com/a/14476/8237):

Lemma 4.(tightness of Chernoff bound) Let $X$ be the average of $k$ independent, 0/1 random variables (r.v.). For any $\epsilon\in(0,1/2]$ and $p\in(0,1/2]$, assuming $\epsilon^2 p k \ge 3$,

(i) If each r.v. is 1 with probability at most $p$, then $$\displaystyle \Pr[X\le (1-\epsilon)p] ~\ge~ \exp\big({-9\epsilon^2 pk}\big).$$

(ii) If each r.v. is 1 with probability at least $p$, then $$\displaystyle \Pr[X\ge (1+\epsilon)p] ~\ge~ \exp\big({-9\epsilon^2 pk}\big).$$

Now consider the problem in the post. Namely, consider the random experiment of throwing $m$ balls into $n$ bins as usual.

1. In any given bin, the expected number of balls is a sum of $m$ independent random 0-1 variables, each with probability $1/n$ of being 1.

2. Fix $\epsilon = \sqrt{\frac{n}{10m} \ln n}$. Call a bin overloaded if it has at least $(1+\epsilon)m/n = m/n + \sqrt{\frac{m}{10n}\ln n}$ balls.

3. By the reverse Chernoff bound (Lemma 4 (ii), with $p=1/n$ and $k=m$), the probability that a given bin is overloaded is at least $$\exp(-9\epsilon^2 m/n) = n^{-9/10}.$$ That is, the probability that a given bin is not overloaded is at most $1-n^{-9/10}$.

4. The events of the form "bin $k$ is not overloaded" for $k\in[n]$ are negatively correlated. Specifically, conditioning on the event that none of the first $k$ bins are overloaded does not decrease the probability that bin $k+1$ is not overloaded. It follows that the probability that none of the $n$ bins are overloaded is at most $(1-n^{-9/10})^n \le \exp(-n^{1/10})$. $~~\Box$