<p>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}&lt;\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$, to yield $p_B &lt; \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}&gt;\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$.</p>

<p>Thus we have $p_B &lt; 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 &lt; \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} &lt; 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)}.$$</p>

<p>Note the summation above is merely a geometric series, so we can simplify this to give $$p_{\geq B} &lt; 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} &lt; 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} &lt; \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)}}.$$</p>

<p>Now, I take it you care about finding some $B$ such that $p_{\geq B} &lt; \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)}.$$</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-27T23:19:36.813Z
this is pretty awesome. thanks for the outline.
Suresh Venkat
CC BY-SA 3.0
2011-04-27T23:32:12.523Z
@Suresh: Glad it's useful.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-27T22:47:30.923Z
2011-04-28T10:56:08.320Z
2011-04-28T10:56:08.320Z
Joe Fitzsimons
<p>For all <span class="math-container">$m\ge n$</span>,the bound is tight up to a factor of <span class="math-container">$\sqrt{10}$</span> in the additive term, in the following sense:</p>
<p><strong>Lemma 1.</strong> <em>The probability that all bins have fewer than <span class="math-container">$m/n + \sqrt{\frac{m}{10n}\ln n}$</span> balls is at most <span class="math-container">$\exp(-n^{1/10})$</span>.</em></p>
<p><em>Proof.</em> The starting point is the tightness of the Chernoff bound.  Specifically, Lemma 4 of <a href="https://doi.org/10.1137/12087222X" rel="nofollow noreferrer">https://doi.org/10.1137/12087222X</a>
(and <a href="https://cstheory.stackexchange.com/a/14476/8237">https://cstheory.stackexchange.com/a/14476/8237</a>):</p>
<p><strong>Lemma 4.</strong>(tightness of Chernoff bound)
<em>Let <span class="math-container">$X$</span> be the average of <span class="math-container">$k$</span> independent, 0/1 random variables (r.v.).
For any <span class="math-container">$\epsilon\in(0,1/2]$</span> and <span class="math-container">$p\in(0,1/2]$</span>,  assuming <span class="math-container">$\epsilon^2 p k \ge 3$</span>,</em></p>
<p>(i)
<em>If each r.v. is 1 with probability at most <span class="math-container">$p$</span>, then</em>
<span class="math-container">$$\displaystyle
\Pr[X\le (1-\epsilon)p]
~\ge~ 
\exp\big({-9\epsilon^2 pk}\big).$$</span></p>
<p>(ii)
<em>If each r.v. is 1 with probability at least <span class="math-container">$p$</span>, then</em>
<span class="math-container">$$\displaystyle
\Pr[X\ge (1+\epsilon)p]
~\ge~ 
\exp\big({-9\epsilon^2 pk}\big).$$</span></p>
<p>Now consider the problem in the post.   Namely, consider the random experiment of throwing <span class="math-container">$m$</span> balls into <span class="math-container">$n$</span> bins as usual.</p>
<ol>
<li><p>In any given bin, the expected number of balls is a sum of <span class="math-container">$m$</span> independent random 0-1 variables, each with probability <span class="math-container">$1/n$</span> of being 1.</p>
</li>
<li><p>Fix <span class="math-container">$\epsilon = \sqrt{\frac{n}{10m} \ln n}$</span>.
Call a bin <em>overloaded</em> if it has at least <span class="math-container">$(1+\epsilon)m/n = m/n + \sqrt{\frac{m}{10n}\ln n}$</span> balls.</p>
</li>
<li><p>By the reverse Chernoff bound (Lemma 4 (ii), with <span class="math-container">$p=1/n$</span> and <span class="math-container">$k=m$</span>), the probability that a given bin is overloaded is at least <span class="math-container">$$\exp(-9\epsilon^2 m/n) = n^{-9/10}.$$</span>
That is, the probability that a given bin is not overloaded is at most <span class="math-container">$1-n^{-9/10}$</span>.</p>
</li>
<li><p>The events of the form <em>&quot;bin <span class="math-container">$k$</span> is not overloaded</em>&quot; for <span class="math-container">$k\in[n]$</span> are negatively correlated.  Specifically, conditioning on the event that none of the first <span class="math-container">$k$</span> bins are overloaded does not decrease the probability that bin <span class="math-container">$k+1$</span> is not overloaded.  It follows that the probability that none of the <span class="math-container">$n$</span> bins are overloaded is at most <span class="math-container">$(1-n^{-9/10})^n \le \exp(-n^{1/10})$</span>.  <span class="math-container">$~~\Box$</span></p>
</li>
</ol>

CC BY-SA 4.0
2022-07-15T21:12:51.503Z
2022-07-15T21:12:51.503Z
Neal Young
<p>It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have <span class="math-container">$O(\log n)$</span> balls in it. In general, one can ask about <span class="math-container">$m &gt; n$</span> balls in <span class="math-container">$n$</span> bins. <a href="https://doi.org/10.1007/3-540-49543-6_13" rel="nofollow noreferrer">A paper from RANDOM 1998 by Raab and Steger</a> explores this in some detail, showing that as <span class="math-container">$m$</span> increases, the probability of going even a little above the expected value of <span class="math-container">$m/n$</span> decreased rapidly. Roughly, setting <span class="math-container">$r = m/n$</span>, they show that the probability of seeing more than <span class="math-container">$r + \sqrt{r\log n}$</span> is <span class="math-container">$o(1)$</span>.</p>
<p>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 <a href="http://siamdl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&amp;id=SMJCAT000035000006001350000001&amp;idtype=cvips" rel="nofollow noreferrer">related paper on the multiple-choice variant</a> co-authored by Angelika Steger in 2006 does not cite any more recent work either.</p>
<p><strong>Update</strong>: In response to Peter's comment, let me clarify the things I'd like to know. I have two goals here.</p>
<ol>
<li>Firstly, I need to know which reference to cite, and it does seem like this is the most recent work on this.</li>
<li>Secondly, it is true that the result is quite tight in the r = 1 range. I'm interested in the m &gt;&gt; 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).</li>
</ol>

CC BY-SA 3.0
2011-04-22T19:47:47.997Z
I learned the name “occupancy problem” from the tag, so thanks for posting an educational question.  :)
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-23T16:05:39.707Z
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.
Peter Shor 
CC BY-SA 3.0
2011-04-24T04:36:03.180Z
@Peter I'll edit the question: it's a valid point.
Suresh Venkat
<reference-request><pr.probability>
Balls and Bins analysis in the m >> n regime
Suresh Venkat
# Balls and Bins analysis in the m >> n regime

(Asked by: username_0 on 2011-04-22)

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](https://doi.org/10.1007/3-540-49543-6_13) 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](http://siamdl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SMJCAT000035000006001350000001&idtype=cvips) 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).

**Tags:** reference-request, pr.probability

> **Comments:**
> **username_1**: I learned the name “occupancy problem” from the tag, so thanks for posting an educational question.  :)  
> **username_2**: 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.  
> **username_0**: @Peter I'll edit the question: it's a valid point.  

---

## 2 answers

### Answer by username_3 on 2011-04-27. Score: 9

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.

> **Comments:**
> **username_0**: this is pretty awesome. thanks for the outline.  
> **username_3**: @Suresh: Glad it's useful.  

---

### Answer by username_4 on 2022-07-15. Score: 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$


---

