<p>The answer is $\Theta(\sqrt{n})$.</p>

<p>First, let's compute $E_{n-1}$.</p>

<p>Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$.</p>

<p>Now, let's look at a different way of distributing balls into bins. We throw a number of balls into each bin chosen from the Poisson distribution, and condition on the event that there are $n$ balls total. I claim that this gives exactly the same distribution as throwing $n$ balls into $n$ bins. Why? It is easy to see that the probability of having $k_j$ balls in the $j$<sup>th</sup> bin is proportional to $\prod_{j=1}^n \frac{1}{k_j!}$ in both distributions.</p>

<p>So let's consider a random walk where at each step, you go from $t$ to $t+1-k$ with probability $\frac{1}{e}\frac{1}{k!}$. I claim that if you condition on the event that this random walk returns to 0 after $n$ steps, the probability that this random always stays above $0$ is the probability that the OP wants to calculate. Why? This height of this random walk after $s$ steps is $s$ minus the number of balls in the first $s$ bins. </p>

<p>If we had chosen a random walk with a probability of $\frac{1}{2}$ of going up or down $1$ on each step, this would be the classical <a href="http://en.wikipedia.org/wiki/Bertrand&#39;s_ballot_theorem">ballot problem</a>, for which the answer is $\frac{1}{2(n-1)}$. This is a variant of the ballot problem which has been studied (see <a href="http://arxiv.org/abs/0802.2491">this paper</a>), and the answer is still $\Theta\left(\frac{1}{n}\right)$.
I don't know whether there is an easy way to compute the constant for the $\Theta\left(\frac{1}{n}\right)$ for this case.</p>

<p>The same paper shows that when the random walk is conditioned to end at height $k$, the probability of always staying positive is $\Theta(k/n)$ as long as $k = O(\sqrt{n})$. This fact will let us estimate $E_s$ for any $s$.</p>

<p>I'm going to be a little handwavy for the rest of my answer, but standard probability techniques can be used to make this rigorous. </p>

<p>We know that as $n$ goes to $\infty$, this random walk converges to a Brownian bridge, i.e., Brownian motion conditioned to start and end at $0$. From general probability theorems, for $\epsilon n &lt; s&lt; (1-\epsilon)n$, the random walk is roughly $\Theta(\sqrt{n})$ away from the $x$-axis. In the case it has height $t&gt;0$, the probability that it has stayed above $0$ for the entire time before $s$ is $\Theta(t/s)$. Since $t$ is likely to be $\Theta(\sqrt{n})$ when $s = \Theta(n)$, we have $E_s \approx \Theta(1/\sqrt{n})$. </p>

CC BY-SA 3.0
2014-08-10T14:47:24.563Z
2014-08-10T19:57:37.187Z
2014-08-10T19:57:37.187Z
Peter Shor 
<p>Exhaustively checking the first few terms (by examining all n^n cases) and a bit of lookup shows that the answer is <a href="https://oeis.org/A036276" rel="nofollow">https://oeis.org/A036276</a> / $n^n$. This implies that the answer is $\sim n^{\frac{1}{2}} \frac{\sqrt{\pi}}{2}$.</p>

<p>More exactly, the answer is:
$$ \frac{n!}{2 n^n} \sum_{k=0}^{n-2}\frac{n^k}{k!} $$
and there is no closed-form answer.</p>

CC BY-SA 3.0
2017-07-27T21:53:08.970Z
Oeis is pretty awesome
Thomas Ahle
CC BY-SA 3.0
2014-08-13T20:40:50.123Z
2014-08-13T21:09:41.930Z
2014-08-13T21:09:41.930Z
Haran
<p>[Edit 2014-08-13: Thanks to a comment by Peter Shor, I have changed my estimate of the asymptotic growth rate of this series.]</p>

<p>My belief is that $\lim_{n\to\infty} \sum_{i&lt;n} \Pr(E_i)$ grows as $\sqrt{n}$. I do not have a proof but I think I have a convincing argument.</p>

<p>Let $B_i = f(i)$ be a random variable that gives the number of balls in bin $i$. Let $B_{i,j} = \sum_{k=i}^j B_k$ be a random variable that gives the total number of balls in bins $i$ through $j$ inclusive.</p>

<p>You can now write $\Pr(E_i) = \sum_{b&lt;j} \Pr(E_j \wedge B_{1,j} = b) \Pr(E_i \mid E_j \wedge B_{1,j} = b)$ for any $j &lt; i$. To that end, let's introduce the functions $\pi$ and $g_i$.</p>

<p>$$\pi(j, k, b) = \Pr(B_j = k \mid B_{1,j-1} = b) = \binom{n-b}{k}\left(\frac{1}{n-j+1}\right)^k\left(\frac{n-j}{n-j+1}\right)^{n-b-k}$$</p>

<p>$$\begin{aligned}
g_i(j, k, b) \; &amp;= \Pr(E_i \wedge B_{j,i} \le k \mid E_{j-1} \wedge B_{1,j-1} = b) \\
&amp;= \begin{cases}
0 &amp; k &lt; 0 \\
1 &amp; k &gt;= 0 \wedge j &gt; i \\
\sum_{l=0}^{j-b-1} \pi(j, l, b) g_i(j + 1, k - l, b + l) &amp; \mathrm{otherwise}
\end{cases}\end{aligned}$$</p>

<p>We can write $\Pr(E_i)$ in terms of $g_i$:</p>

<p>$$ \Pr(E_i) = g_i(1, i - 1, 0) $$</p>

<p>Now, it's clear from the definition of $g_i$ that</p>

<p>$$ \Pr(E_i) = \frac{(n-i)^{n-i+1}}{n^n}h_i(n) $$</p>

<p>where $h_i(n)$ is a polynomial in $n$ of degree $i - 1$. This makes some intuitive sense too; at least $n - i + 1$ balls will have to be put in one of the $(i+1)$th through $n$th bins (of which there are $n-i$).</p>

<p>Since we're only talking about $Pr(E_i)$ when $n\to\infty$, only the lead coefficient of $h_i(n)$ is relevant; let's call this coefficient $a_i$. Then</p>

<p>$$ \lim_{n\to\infty} \Pr(E_i) = \frac{a_i}{e^i} $$</p>

<p>How do we compute $a_i$? Well, this is where I'll do a little handwaving. If you work out the first few $E_i$, you'll see that a pattern emerges in the computation of this coefficient. You can write it as</p>

<p>$$ a_i = \mu_i(1, i-1, 0) $$
where
$$ \mu_i(j, k, b) = \begin{cases}
0 &amp; k &lt; 0 \\
1 &amp; k &gt;= 0 \wedge i &gt; j \\
\sum_{l = 0}^{j-b-1} \frac{1}{l!} \mu_i(j + 1, k - l, b+ l) &amp; \mathrm{otherwise}
\end{cases}$$</p>

<p>Now, I wasn't able to derive a closed-form equivalent directly, but I computed the first 20 values of $Pr(E_i)$:</p>

<pre><code>N       a_i/e^i
1       0.367879
2       0.270671
3       0.224042
4       0.195367
5       0.175467
6       0.160623
7       0.149003
8       0.139587
9       0.131756
10      0.12511
11      0.119378
12      0.114368
13      0.10994
14      0.105989
15      0.102436
16      0.0992175
17      0.0962846
18      0.0935973
19      0.0911231
20      0.0888353
</code></pre>

<p>Now, it turns out that 
$$ \DeclareMathOperator{\Pois}{Pois} \Pr(E_i) = \frac{i^i}{i! e^i} = \Pois(i; i) $$</p>

<p>where $\Pois(i; \lambda)$ is the probability that a random variable $X$ has value $i$ when it's drawn from a Poisson distribution with mean $\lambda$. Thus we can write our sum as</p>

<p>$$ \lim_{n\to\infty} \sum_{i=1}^n \Pr(E_i) = \sum_{x = 1}^{\infty} \frac{x^x}{x!e^x} $$</p>

<p><a href="http://www.wolframalpha.com/input/?i=sum%28e%5E-x+*+x%5Ex+%2F+x%21%2C+x+%3D+1+to+infinity%29" rel="nofollow">Wolfram Alpha tells me this series diverges</a>. Peter Shor points out in a comment that Stirling's approximation allows us to estimate $\Pr(E_i)$:</p>

<p>$$ \lim_{n\to\infty} \Pr(E_x) = \frac{x^x}{x!e^x} \approx \frac{1}{\sqrt{2 \pi x}}$$</p>

<p>Let</p>

<p>$$ \phi(x) = \frac{1}{\sqrt{2 \pi x}} $$</p>

<p>Since</p>

<ul>
<li>$\lim_{x\to\infty}\frac{\phi(x)}{\phi(x+1)} = 1$</li>
<li>$\phi(x)$ is decreasing</li>
<li>$\int_1^n \phi(x)dx \to \infty$ as $n \to \infty$</li>
</ul>

<p>our series grows as $\int_1^n \phi(x) dx$ (See e.g. <a href="http://www.math.uconn.edu/~kconrad/blurbs/analysis/sumest.pdf" rel="nofollow">Theorem 2</a>). That is,</p>

<p>$$\sum_{i=1}^n Pr(E_i) = \Theta\left(\sqrt{n}\right)$$</p>

CC BY-SA 3.0
2014-08-13T02:06:28.303Z
Wolfram Alpha is wrong. Use [Stirling's formula](http://en.wikipedia.org/wiki/Stirling's_approximation). It says that, $x^x/(x! e^x)\approx 1/\sqrt{2\pi x}$.
Peter Shor 
CC BY-SA 3.0
2014-08-13T04:42:47.570Z
@PeterShor Thanks! I've updated the conclusion thanks to your insight, and now I am in agreement with the other two answers. It's interesting to me to see 3 quite different approaches to this problem.
ruds
CC BY-SA 3.0
2014-08-11T04:15:29.370Z
2014-08-13T04:39:31.573Z
2014-08-13T04:39:31.573Z
ruds
<p>EDIT: (2014-08-08)
As Douglas Zare points out in the comments, the argument below, specifically the 'bridge' between the two probabilities, is incorrect.  I don't see a straight forward way to fix it.  I'll leave the answer here as I believe it still provides some intuition, but know that $$ \Pr(E_m) \le \prod_{l=1}^{m}\Pr(F_l) $$ is <strong>not</strong> true in general.</p>

<hr>

<p>This won't be a complete answer but hopefully it will have enough content that you or someone more knowledgeable than myself can finish it off.</p>

<p>Consider the probability of exactly $k$ balls falling into the first $l$ (of $n$) bins:</p>

<p>$$ \binom{n}{k} \left( \frac{l}{n} \right)^k \left(\frac{n-l}{n} \right)^{n-k} $$</p>

<p>Call the probability that fewer than $l$ balls fall into the first $l$ bins $F_l$:</p>

<p>$$ \Pr(F_l) = \sum_{k=0}^{l-1} \binom{n}{k} \left( \frac{l}{n} \right)^k \left( \frac{n-l}{n} \right)^{n-k} $$</p>

<p>The probability that the event, $E_l$, above occurs is less than if we considered each of the $F_l$ events occurring independently and all at once.  This gives us a bridge between the two:</p>

<p>$$ \begin{array}{lll} \Pr(E_m) &amp; \le &amp; \prod_{l=1}^m \Pr(F_l) \\
  &amp; = &amp; \prod_{l=1}^m \left( \sum_{k=1}^{l-1} \binom{n}{k} \left( \frac{l}{n}^k \right) \left( \frac{n-l}{n} \right)^{n-k} \right) \\
 &amp; = &amp; \prod_{l=1}^m F(l-1; n, \frac{l}{n} )
\end{array} $$</p>

<p>Where $F(l-1; n, \frac{l}{n})$ is the <a href="http://en.wikipedia.org/wiki/Binomial_distribution#Cumulative_distribution_function" rel="nofollow noreferrer">cumulative distribution function for the Binomial distribution</a> with $p = \frac{l}{n}$.  Just reading a few lines down on the Wikipedia page, and noting that $(l-1 \le p n)$, we can use <a href="http://en.wikipedia.org/wiki/Chernoff%27s_inequality" rel="nofollow noreferrer">Chernoff's inequality</a> to get:</p>

<p>$$
\begin{array}{lll}
\Pr(E_m) &amp; \le &amp; \prod_{l=1}^m \exp\left[ -\frac{1}{2l} \right] \\
 &amp; = &amp; \exp\left[ - \frac{1}{2} \sum_{l=1}^m \frac{1}{l} \right] \\
 &amp; = &amp; \exp\left[ - \frac{1}{2} H_m \right] \\
 &amp; \le &amp; \exp\left[ -\frac{1}{2} \left( \frac{1}{2 m} + \ln(m) + \gamma \right) \right]
\end{array}
$$</p>

<p>Where $H_m$ is the $m$'th <a href="http://mathworld.wolfram.com/HarmonicNumber.html" rel="nofollow noreferrer">Harmonic Number</a>, $\gamma$ is the Euler-Mascheroni constant and the inequality for the $H_m$ is taken from Wolfram's MathWorld linked page.</p>

<p>Not worrying about the $e^{-1/4m}$ factor, this finally gives us:</p>

<p>$$ \Pr(E_m) \le \frac{ e^{ -\gamma/2}}{\sqrt{m}} $$</p>

<p>Below is a log-log plot of an average of 100,000 instances for $n=2048$ as a function of $m$ with the function $\frac{e^{ -\gamma/2}}{\sqrt{m}}$ also plotted for reference:</p>

<p><img src="https://i.sstatic.net/KZtG8.png" alt="enter image description here"></p>

<p>While the constants are off, the form of the function appears to be correct.  </p>

<p>Below is a log-log plot for varying $n$ with each point being the average of 100,000 instances as a function of $m$:</p>

<p><img src="https://i.sstatic.net/UDSpO.png" alt="enter image description here"></p>

<p>Finally, getting to the original question you wanted answered, since we know that $\Pr(E_m) \propto \frac{1}{\sqrt{m}}$ we have:</p>

<p>$$ \sum_{i&lt;n} \Pr(E_i) \propto \sqrt{n} $$</p>

<p>And as numerical verification, below is a log-log plot of the sum, $S$, versus instance size, $n$.  Each point represents the average of the sum of 100,000
instances.  The function $x^{1/2}$ has been plotted for reference:</p>

<p><img src="https://i.sstatic.net/BgRGZ.png" alt="enter image description here"></p>

<p>While I see no direct connection between the two, the tricks and final form of this problem have a lot of commonalities with the Birthday Problem as initially guessed at in the comments.</p>

CC BY-SA 3.0
2014-08-05T23:23:24.697Z
How do you get $Pr(E_2) \le Pr(F_1)\times Pr(F_2)$? For example, for $n=100$, I calculate that $Pr(E_2) = 0.267946 \gt 0.14761 = Pr(F_1)Pr(F_2).$ If you are told that the first bin is empty, does this make it more or less likely that the first two bins hold at most $1$ ball? It's more likely, so $Pr(F_1)Pr(F_2)$ is an underestimate.
Douglas Zare
CC BY-SA 3.0
2014-08-09T02:56:05.407Z
@DouglasZare, I've verified your calculations, you're correct.  Serves me right for not being more rigorous.
user834
CC BY-SA 3.0
2012-04-30T06:52:23.077Z
2014-08-09T03:02:22.233Z
2014-08-09T03:02:22.233Z
user834
<p>This is not a homework, though it looks like. Any reference is welcome. :-)</p>

<p><strong>Scenario:</strong> There are $n$ <strong>different</strong> balls and $n$ <strong>different</strong> bins (labled from 1 to $n$, from left to right). Each ball is thrown independently and uniformly into bins. Let $f(i)$ be the number of balls in the $i$~th bin. Let $E_i$ denote the following event.</p>

<blockquote>
  <p>For each $j\le i$, $\sum_{k\le j}{f(k)} \le j-1$</p>
</blockquote>

<p>That is, the first $j$ bins (the most left $j$ bins) contains less than $j$ balls, for each $j\le i$. </p>

<p><strong>Question:</strong> Estimate $\sum_{i&lt;n}{Pr(E_i)}$, in terms of $n$? When $n$ goes infinity. A lowerbound is preferred. I do not think an easily calculated formula exisit.</p>

<p><strong>Example:</strong> $\lim\limits_{n\to\infty}{Pr(E_1)}=\lim\limits_{n\to\infty}{(\frac{n-1}{n})^n}=\frac{1}{e}$.  Note $Pr(E_n)=0$.</p>

<p><strong>My guess:</strong> I guess $\sum_{i&lt;n}{Pr(E_i)}=\ln n$, when $n$ goes infinity. I considered the first $\ln n$ items in the summation.</p>

CC BY-SA 3.0
2012-03-21T14:16:51.183Z
It looks like a subcase from the birthday problem..
Gopi
CC BY-SA 3.0
2012-03-21T14:30:18.093Z
@Gopi I cannot convince myself that my question is a restricted birthday problem. Can you explicitly explain it? Thank you very much. Note: The constraint is on the sum of balls in the first $j$ bins, not on the number of bins on specific bin.
Peng Zhang
CC BY-SA 3.0
2012-03-21T14:36:24.123Z
Indeed, my bad, after re-reading the wikipedia article on the birthday problem I realised I was considering another problem that was adapted from the Birthday problem.
Gopi
CC BY-SA 3.0
2012-03-21T14:40:29.720Z
(and even then I was wrong, I misread the question :s)
Gopi
CC BY-SA 3.0
2012-03-21T14:49:28.193Z
@Gopi I wish you like it. It arises from a problem I am studying. And I tried it more than one month. :-(
Peng Zhang
CC BY-SA 3.0
2012-03-21T15:28:37.443Z
So the bins are distinguished in some way? or are you really doing a sort by bin capacity first ?
Suresh Venkat
CC BY-SA 3.0
2012-03-21T15:52:19.463Z
@SureshVenkat The bins are different, labeled from 1 to $n$, from left to right. I do not know what does "sort by bin capacity first" mean? Thank you very much for comment.
Peng Zhang
CC BY-SA 3.0
2012-03-21T15:53:16.010Z
in other words, I can't permute the bins to order them in increasing order of f(k)
Suresh Venkat
CC BY-SA 3.0
2012-03-22T05:37:43.337Z
Some incorrect ideas...

So think about how to encode a state: Read the bins form left to right. If the first bin has i balls, output a sequence of i ones, followed by a 0. Do this for all the bins from left to right. You codition seems to be that you are interested in the biggest i such that this binary string (that has n zeros and n ones) for the first time it contains more ones than zeros. 

Now, lets make a leap of fate and generate the 0 and 1 with equal probability $1/2$. (This might be complete nonsense). This problem is related to Catalan numbers and Dyck words. And...???
Sariel Har-Peled
CC BY-SA 3.0
2012-03-22T07:49:50.857Z
@SarielHar-Peled Thank you so much. There are two differences:1. balls are different. 2. "ones less than zeros" in some specific positions. unlike dyck word on every position.
Peng Zhang
CC BY-SA 3.0
2012-03-22T15:04:00.090Z
I dont see in your defnition why it matters that the balls are different. Also, the string intepetation takes into accoutn the fact that the bins are different.
Sariel Har-Peled
<reference-request><co.combinatorics><pr.probability>
Throwing Balls into Bins, estimate a lowerbound of its probability
Peng Zhang
# Throwing Balls into Bins, estimate a lowerbound of its probability

(Asked by: username_0 on 2012-03-21)

This is not a homework, though it looks like. Any reference is welcome. :-)

**Scenario:** There are $n$ **different** balls and $n$ **different** bins (labled from 1 to $n$, from left to right). Each ball is thrown independently and uniformly into bins. Let $f(i)$ be the number of balls in the $i$~th bin. Let $E\_i$ denote the following event.

> For each $j\le i$, $\sum\_{k\le j}{f(k)} \le j-1$

That is, the first $j$ bins (the most left $j$ bins) contains less than $j$ balls, for each $j\le i$.

**Question:** Estimate $\sum\_{i

**Example:** $\lim\limits\_{n\to\infty}{Pr(E\_1)}=\lim\limits\_{n\to\infty}{(\frac{n-1}{n})^n}=\frac{1}{e}$. Note $Pr(E\_n)=0$.

**My guess:** I guess $\sum\_{i

**Tags:** reference-request, co.combinatorics, pr.probability
> **Comments:**
> **username_1**: It looks like a subcase from the birthday problem..  
> **username_0**: @Gopi I cannot convince myself that my question is a restricted birthday problem. Can you explicitly explain it? Thank you very much. Note: The constraint is on the sum of balls in the first $j$ bins, not on the number of bins on specific bin.  
> **username_1**: Indeed, my bad, after re-reading the wikipedia article on the birthday problem I realised I was considering another problem that was adapted from the Birthday problem.  
> **username_1**: (and even then I was wrong, I misread the question :s)  
> **username_0**: @Gopi I wish you like it. It arises from a problem I am studying. And I tried it more than one month. :-(  
> **username_2**: So the bins are distinguished in some way? or are you really doing a sort by bin capacity first ?  
> **username_0**: @SureshVenkat The bins are different, labeled from 1 to $n$, from left to right. I do not know what does "sort by bin capacity first" mean? Thank you very much for comment.  
> **username_2**: in other words, I can't permute the bins to order them in increasing order of f(k)  
> **username_3**: Some incorrect ideas...  So think about how to encode a state: Read the bins form left to right. If the first bin has i balls, output a sequence of i ones, followed by a 0. Do this for all the bins from left to right. You codition seems to be that you are interested in the biggest i such that this binary string (that has n zeros and n ones) for the first time it contains more ones than zeros.   Now, lets make a leap of fate and generate the 0 and 1 with equal probability $1/2$. (This might be complete nonsense). This problem is related to Catalan numbers and Dyck words. And...???  
> **username_0**: @SarielHar-Peled Thank you so much. There are two differences:1. balls are different. 2. "ones less than zeros" in some specific positions. unlike dyck word on every position.  
> **username_3**: I dont see in your defnition why it matters that the balls are different. Also, the string intepetation takes into accoutn the fact that the bins are different.  

---

## 4 answers

### Answer by username_8 on 2012-04-30. Score: 11 | Accepted answer

EDIT: (2014-08-08)
As Douglas Zare points out in the comments, the argument below, specifically the 'bridge' between the two probabilities, is incorrect. I don't see a straight forward way to fix it. I'll leave the answer here as I believe it still provides some intuition, but know that $$ \Pr(E\_m) \le \prod\_{l=1}^{m}\Pr(F\_l) $$ is **not** true in general.

---

This won't be a complete answer but hopefully it will have enough content that you or someone more knowledgeable than myself can finish it off.

Consider the probability of exactly $k$ balls falling into the first $l$ (of $n$) bins:

$$ \binom{n}{k} \left( \frac{l}{n} \right)^k \left(\frac{n-l}{n} \right)^{n-k} $$

Call the probability that fewer than $l$ balls fall into the first $l$ bins $F\_l$:

$$ \Pr(F\_l) = \sum\_{k=0}^{l-1} \binom{n}{k} \left( \frac{l}{n} \right)^k \left( \frac{n-l}{n} \right)^{n-k} $$

The probability that the event, $E\_l$, above occurs is less than if we considered each of the $F\_l$ events occurring independently and all at once. This gives us a bridge between the two:

$$ \begin{array}{lll} \Pr(E\_m) & \le & \prod\_{l=1}^m \Pr(F\_l) \\
& = & \prod\_{l=1}^m \left( \sum\_{k=1}^{l-1} \binom{n}{k} \left( \frac{l}{n}^k \right) \left( \frac{n-l}{n} \right)^{n-k} \right) \\
& = & \prod\_{l=1}^m F(l-1; n, \frac{l}{n} )
\end{array} $$

Where $F(l-1; n, \frac{l}{n})$ is the [cumulative distribution function for the Binomial distribution](http://en.wikipedia.org/wiki/Binomial_distribution#Cumulative_distribution_function) with $p = \frac{l}{n}$. Just reading a few lines down on the Wikipedia page, and noting that $(l-1 \le p n)$, we can use [Chernoff's inequality](http://en.wikipedia.org/wiki/Chernoff%27s_inequality) to get:

$$
\begin{array}{lll}
\Pr(E\_m) & \le & \prod\_{l=1}^m \exp\left[ -\frac{1}{2l} \right] \\
& = & \exp\left[ - \frac{1}{2} \sum\_{l=1}^m \frac{1}{l} \right] \\
& = & \exp\left[ - \frac{1}{2} H\_m \right] \\
& \le & \exp\left[ -\frac{1}{2} \left( \frac{1}{2 m} + \ln(m) + \gamma \right) \right]
\end{array}
$$

Where $H\_m$ is the $m$'th [Harmonic Number](http://mathworld.wolfram.com/HarmonicNumber.html), $\gamma$ is the Euler-Mascheroni constant and the inequality for the $H\_m$ is taken from Wolfram's MathWorld linked page.

Not worrying about the $e^{-1/4m}$ factor, this finally gives us:

$$ \Pr(E\_m) \le \frac{ e^{ -\gamma/2}}{\sqrt{m}} $$

Below is a log-log plot of an average of 100,000 instances for $n=2048$ as a function of $m$ with the function $\frac{e^{ -\gamma/2}}{\sqrt{m}}$ also plotted for reference:

![enter image description here](https://i.sstatic.net/KZtG8.png)

While the constants are off, the form of the function appears to be correct.

Below is a log-log plot for varying $n$ with each point being the average of 100,000 instances as a function of $m$:

![enter image description here](https://i.sstatic.net/UDSpO.png)

Finally, getting to the original question you wanted answered, since we know that $\Pr(E\_m) \propto \frac{1}{\sqrt{m}}$ we have:

$$ \sum\_{i

And as numerical verification, below is a log-log plot of the sum, $S$, versus instance size, $n$. Each point represents the average of the sum of 100,000
instances. The function $x^{1/2}$ has been plotted for reference:

![enter image description here](https://i.sstatic.net/BgRGZ.png)

While I see no direct connection between the two, the tricks and final form of this problem have a lot of commonalities with the Birthday Problem as initially guessed at in the comments.

> **Comments:**
> **username_9**: How do you get $Pr(E_2) \le Pr(F_1)\times Pr(F_2)$? For example, for $n=100$, I calculate that $Pr(E_2) = 0.267946 \gt 0.14761 = Pr(F_1)Pr(F_2).$ If you are told that the first bin is empty, does this make it more or less likely that the first two bins hold at most $1$ ball? It's more likely, so $Pr(F_1)Pr(F_2)$ is an underestimate.  
> **username_8**: @DouglasZare, I've verified your calculations, you're correct.  Serves me right for not being more rigorous.  

---

### Answer by username_4 on 2014-08-10. Score: 15

The answer is $\Theta(\sqrt{n})$.

First, let's compute $E\_{n-1}$.

Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$.

Now, let's look at a different way of distributing balls into bins. We throw a number of balls into each bin chosen from the Poisson distribution, and condition on the event that there are $n$ balls total. I claim that this gives exactly the same distribution as throwing $n$ balls into $n$ bins. Why? It is easy to see that the probability of having $k\_j$ balls in the $j$th bin is proportional to $\prod\_{j=1}^n \frac{1}{k\_j!}$ in both distributions.

So let's consider a random walk where at each step, you go from $t$ to $t+1-k$ with probability $\frac{1}{e}\frac{1}{k!}$. I claim that if you condition on the event that this random walk returns to 0 after $n$ steps, the probability that this random always stays above $0$ is the probability that the OP wants to calculate. Why? This height of this random walk after $s$ steps is $s$ minus the number of balls in the first $s$ bins.

If we had chosen a random walk with a probability of $\frac{1}{2}$ of going up or down $1$ on each step, this would be the classical [ballot problem](http://en.wikipedia.org/wiki/Bertrand's_ballot_theorem), for which the answer is $\frac{1}{2(n-1)}$. This is a variant of the ballot problem which has been studied (see [this paper](http://arxiv.org/abs/0802.2491)), and the answer is still $\Theta\left(\frac{1}{n}\right)$.
I don't know whether there is an easy way to compute the constant for the $\Theta\left(\frac{1}{n}\right)$ for this case.

The same paper shows that when the random walk is conditioned to end at height $k$, the probability of always staying positive is $\Theta(k/n)$ as long as $k = O(\sqrt{n})$. This fact will let us estimate $E\_s$ for any $s$.

I'm going to be a little handwavy for the rest of my answer, but standard probability techniques can be used to make this rigorous.

We know that as $n$ goes to $\infty$, this random walk converges to a Brownian bridge, i.e., Brownian motion conditioned to start and end at $0$. From general probability theorems, for $\epsilon n < s< (1-\epsilon)n$, the random walk is roughly $\Theta(\sqrt{n})$ away from the $x$-axis. In the case it has height $t>0$, the probability that it has stayed above $0$ for the entire time before $s$ is $\Theta(t/s)$. Since $t$ is likely to be $\Theta(\sqrt{n})$ when $s = \Theta(n)$, we have $E\_s \approx \Theta(1/\sqrt{n})$.


---

### Answer by username_5 on 2014-08-13. Score: 4

Exhaustively checking the first few terms (by examining all n^n cases) and a bit of lookup shows that the answer is <https://oeis.org/A036276> / $n^n$. This implies that the answer is $\sim n^{\frac{1}{2}} \frac{\sqrt{\pi}}{2}$.

More exactly, the answer is:
$$ \frac{n!}{2 n^n} \sum\_{k=0}^{n-2}\frac{n^k}{k!} $$
and there is no closed-form answer.

> **Comments:**
> **username_6**: Oeis is pretty awesome  

---

### Answer by username_7 on 2014-08-11. Score: 4

[Edit 2014-08-13: Thanks to a comment by Peter Shor, I have changed my estimate of the asymptotic growth rate of this series.]
My belief is that $\lim_{n\to\infty} \sum_{i
Let $B_i = f(i)$ be a random variable that gives the number of balls in bin $i$. Let $B_{i,j} = \sum_{k=i}^j B_k$ be a random variable that gives the total number of balls in bins $i$ through $j$ inclusive.
You can now write $\Pr(E_i) = \sum_{b
$$\pi(j, k, b) = \Pr(B_j = k \mid B_{1,j-1} = b) = \binom{n-b}{k}\left(\frac{1}{n-j+1}\right)^k\left(\frac{n-j}{n-j+1}\right)^{n-b-k}$$
$$\begin{aligned}
g_i(j, k, b) \; &= \Pr(E_i \wedge B_{j,i} \le k \mid E_{j-1} \wedge B_{1,j-1} = b) \\
&= \begin{cases}
0 & k < 0 \\
1 & k >= 0 \wedge j > i \\
\sum_{l=0}^{j-b-1} \pi(j, l, b) g_i(j + 1, k - l, b + l) & \mathrm{otherwise}
\end{cases}\end{aligned}$$
We can write $\Pr(E_i)$ in terms of $g_i$:
$$ \Pr(E_i) = g_i(1, i - 1, 0) $$
Now, it's clear from the definition of $g_i$ that
$$ \Pr(E_i) = \frac{(n-i)^{n-i+1}}{n^n}h_i(n) $$
where $h_i(n)$ is a polynomial in $n$ of degree $i - 1$. This makes some intuitive sense too; at least $n - i + 1$ balls will have to be put in one of the $(i+1)$th through $n$th bins (of which there are $n-i$).
Since we're only talking about $Pr(E_i)$ when $n\to\infty$, only the lead coefficient of $h_i(n)$ is relevant; let's call this coefficient $a_i$. Then
$$ \lim_{n\to\infty} \Pr(E_i) = \frac{a_i}{e^i} $$
How do we compute $a_i$? Well, this is where I'll do a little handwaving. If you work out the first few $E_i$, you'll see that a pattern emerges in the computation of this coefficient. You can write it as
$$ a_i = \mu_i(1, i-1, 0) $$
where
$$ \mu_i(j, k, b) = \begin{cases}
0 & k < 0 \\
1 & k >= 0 \wedge i > j \\
\sum_{l = 0}^{j-b-1} \frac{1}{l!} \mu_i(j + 1, k - l, b+ l) & \mathrm{otherwise}
\end{cases}$$
Now, I wasn't able to derive a closed-form equivalent directly, but I computed the first 20 values of $Pr(E_i)$:
N       a_i/e^i
1       0.367879
2       0.270671
3       0.224042
4       0.195367
5       0.175467
6       0.160623
7       0.149003
8       0.139587
9       0.131756
10      0.12511
11      0.119378
12      0.114368
13      0.10994
14      0.105989
15      0.102436
16      0.0992175
17      0.0962846
18      0.0935973
19      0.0911231
20      0.0888353

Now, it turns out that 
$$ \DeclareMathOperator{\Pois}{Pois} \Pr(E_i) = \frac{i^i}{i! e^i} = \Pois(i; i) $$
where $\Pois(i; \lambda)$ is the probability that a random variable $X$ has value $i$ when it's drawn from a Poisson distribution with mean $\lambda$. Thus we can write our sum as
$$ \lim_{n\to\infty} \sum_{i=1}^n \Pr(E_i) = \sum_{x = 1}^{\infty} \frac{x^x}{x!e^x} $$
Wolfram Alpha tells me this series diverges. Peter Shor points out in a comment that Stirling's approximation allows us to estimate $\Pr(E_i)$:
$$ \lim_{n\to\infty} \Pr(E_x) = \frac{x^x}{x!e^x} \approx \frac{1}{\sqrt{2 \pi x}}$$
Let
$$ \phi(x) = \frac{1}{\sqrt{2 \pi x}} $$
Since

$\lim_{x\to\infty}\frac{\phi(x)}{\phi(x+1)} = 1$
$\phi(x)$ is decreasing
$\int_1^n \phi(x)dx \to \infty$ as $n \to \infty$

our series grows as $\int_1^n \phi(x) dx$ (See e.g. Theorem 2). That is,
$$\sum_{i=1}^n Pr(E_i) = \Theta\left(\sqrt{n}\right)$$

> **Comments:**
> **username_4**: Wolfram Alpha is wrong. Use [Stirling's formula](http://en.wikipedia.org/wiki/Stirling's_approximation). It says that, $x^x/(x! e^x)\approx 1/\sqrt{2\pi x}$.  
> **username_7**: @PeterShor Thanks! I've updated the conclusion thanks to your insight, and now I am in agreement with the other two answers. It's interesting to me to see 3 quite different approaches to this problem.  

---

