$n$ balls are thrown randomly into $k$ bins - how many are empty?

11.5k Views Asked by At

A large number of variants of this question were already asked here, including these - one, two, which are close, but none seem to answer my question.

Assume that $n$ balls are thrown randomly and independently into $k$ bins.

What is the probability of finding $x$ empty bins?

What is the expectation of the number of empty bins?

2

There are 2 best solutions below

6
On BEST ANSWER

We do the expectation, without finding the distribution. Let $X_i=1$ if Bin $i$ is empty, and let $X_i=0$ otherwise. Then the number of empty bins is $X_1+\cdots+X_k$, and the expected number is $E(X_1)+\cdots+E(X_k)$.

The probability Bin $i$ is empty is $\left(\frac{k-1}{k}\right)^n$. Thus $E(X_i)=\left(\frac{k-1}{k}\right)^n$. Multiply by $k$ for the expected number of empty bins.

1
On

The OP is more concerned with the first question, what is the probability of $x$ empty bins.

Let me try. Start with $x=1$. Thus, all remaining $k-1$ bins are NOT empty. The total number of put $n$ balls into $k-1$ bins is standard and many solutions online, the number is $C_{n+k-2}^{k-2}$. This includes the situations that some bins are EMPTY. So if every bin is NOT empty, thus the total number of ways is to put $n-(k-1)$ balls into $k-1$ bins (assume every bin has already 1 ball). It has $C_{n-1}^{k-2}$ ways. Thus, $$Prob(x=1) = n*\frac{C_{n-1}^{k-2}}{C_{n+k-2}^{k-2}}$$ The reason we multiply by $n$ is because of $C_n^1$ ways to choose which box is empty.

I believe other situations for $x$ can be derived in a similar way.