14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It looks like a subcase from the birthday problem.. $\endgroup$ – Gopi Mar 21 '12 at 14:16
  • $\begingroup$ @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. $\endgroup$ – Peng Zhang Mar 21 '12 at 14:30
  • $\begingroup$ 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. $\endgroup$ – Gopi Mar 21 '12 at 14:36
  • 2
    $\begingroup$ 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...??? $\endgroup$ – Sariel Har-Peled Mar 22 '12 at 5:37
  • 4
    $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Mar 22 '12 at 15:04
11
$\begingroup$

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:

enter image description here

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

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:

enter image description here

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Douglas Zare Aug 5 '14 at 23:23
  • $\begingroup$ @DouglasZare, I've verified your calculations, you're correct. Serves me right for not being more rigorous. $\endgroup$ – user834 Aug 9 '14 at 2:56
15
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Wolfram Alpha is wrong. Use Stirling's formula. It says that, $x^x/(x! e^x)\approx 1/\sqrt{2\pi x}$. $\endgroup$ – Peter Shor Aug 13 '14 at 2:06
  • $\begingroup$ @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. $\endgroup$ – ruds Aug 13 '14 at 4:42
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oeis is pretty awesome $\endgroup$ – Thomas Ahle Jul 27 '17 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.