Probability – If n Balls are Thrown into k Bins, What is the Probability that Every Bin Gets at Least One Ball?

balls-in-binsprobability

If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what is $P(X=0)$?

I was able to calculate the $E(X)$ and thus bound with Markov's inequality $P(X \geq 1) \le E(X)$ but I don't how to work out an exact answer.

http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/588.596.pdf

Best Answer

What is the chance that all $k$ bins are occupied?

For $1\leq i\leq k$, define $A_i$ to be the event that the $i$th bin stays empty. These are exchangeable events with $P(A_1\cdots A_j)=(1-{j\over k})^n$ and so by inclusion-exclusion, the probability that there are no empty bins is $$P(X=0)=\sum_{j=0}^k (-1)^j {k\choose j}\left(1-{j\over k}\right)^n.$$

Stirling numbers of the second kind can be used to give an alternative solution to the occupancy problem. We can fill all $k$ bins as follows: partition the balls $\{1,2,\dots, n\}$ into $k$ non-empty sets, then assign the bin values $1,2,\dots, k$ to these sets. There are ${n\brace k}$ partitions, and for each partition $k!$ ways to assign the bin values. Thus, $$P(X=0)={{n\brace k}\,k!\over k^n}.$$