3
$\begingroup$

Suppose we throw $n$ indistinguishable balls in $n$ bins at random. The throws are independent. What is the expected number of empty bins? What is the expected number of bins with one ball.

Using indicator random variables, expectations, some sloppy math and some questionable logic, I arrive at the conclusion that both are approximately $n/e$. I'm not able to find simple formulas. It also sounds very counter-intuitive to me.

Worse, I wrote a small Ruby program to simulate it and the results appear to be (approximately) correct.

Can anybody show me a good solution?

$\endgroup$
0

1 Answer 1

8
$\begingroup$

The expected number of empties has been done endlessly. So we do the expected number with $1$ ball. Let $X_i=1$ if Bin $i$ has $1$ ball, and let $X_i=0$ otherwise.

The probability that $X_i=1$ is the probability that one of the $n$ balls falls into Bin $i$, and the others don't. This probability is $\binom{n}{1}\frac{1}{n}\left(1-\frac{1}{n}\right)^{n-1}$, which simplifies to $\left(1-\frac{1}{n}\right)^{n-1}$.

Let random variable $Y_1(n)$ be the number of bins with $1$ ball. Then $Y_1(n)=X_1+\cdots+X_n$, and therefore by the linearity of expectation we have $$E(Y_1(n))=n\left(1-\frac{1}{n}\right)^{n-1}.$$ And indeed $$\lim_{n\to\infty}\frac{E(Y_1(n))}{n}=\lim_{n\to\infty} \left(1-\frac{1}{n}\right)^{n-1}=e^{-1}.$$

$\endgroup$
3
  • $\begingroup$ Sorry, could you please shed some light on this formula $\binom{n}{1}\frac{1}{n}\left(1-\frac{1}{n}\right)^{n-1}.$ I see that $\frac{1}{n}$ is probability, that ball got into certain bin, $\left(1-\frac{1}{n}\right)^{n-1}$ that it doesn't in $n-1$ steps. $\endgroup$
    – Yola
    Nov 4, 2014 at 11:28
  • 2
    $\begingroup$ We are repeating an experiment $n$ times, with each time probability of success $1/n$, of failure therefore $1-1/n$. By the binomial distribution the probability of exactly $1$ success in $n$ trials is $\binom{n}{1}(1/n)^1(1-1/n)^{n-1}$. $\endgroup$ Nov 4, 2014 at 13:20
  • $\begingroup$ Big thanks! and upvote:) $\endgroup$
    – Yola
    Nov 5, 2014 at 7:36

Not the answer you're looking for? Browse other questions tagged .