Throwing Balls into Bins, estimate a lowerbound of its probability 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&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.

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&lt;n}{Pr(E_i)}=\ln n$, when $n$ goes infinity. I considered the first $\ln n$ items in the summation.
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, 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), 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 &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})$.