Throwing Balls into Bins, estimate a lowerbound of its probability

Question

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

Answer 1

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 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 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, $\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:

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$:

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<n} \Pr(E_i) \propto \sqrt{n} $$

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:

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.

Answer 2

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 < 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 3

[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<n} \Pr(E_i)$ grows as $\sqrt{n}$. I do not have a proof but I think I have a convincing argument.

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<j} \Pr(E_j \wedge B_{1,j} = b) \Pr(E_i \mid E_j \wedge B_{1,j} = b)$ for any $j < i$. To that end, let's introduce the functions $\pi$ and $g_i$.

$$\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)$$

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