Probability – Calculate Probability of Exactly k Bins Being Empty

balls-in-binsbinomial distributionprobability

I've searched for an understandable answer to this exact question and have failed to find it.

How do you find the probability that exactly $k$ bins are empty, given $m$ balls and $n$ bins? (Each ball drop is independent).

The solution to this similar question does not explain how to find the probability that exactly $k$ bins are empty. It mentions the solution in passing in the comments, but does not thoroughly explain how to find the answer.

Best Answer

(This is basically the same as true blue anil's answer) Let's count the ways in which $m$ distinguishable balls can be placed in $n$ bins.

Then the total number of possible ways is $n^m$

The "favorable" ways are those that have exactly $r=n-k\le m$ non-empty bins. There are $r! \, S(m,r) \, {n \choose r}$, where

  • $r!$ counts the permutations of bins.
  • $S(m,r)$ is the Stirling number of the second kind, which count the number of ways of placing $m$ balls in $r$ unlabelled bins.
  • ${n \choose r}$ counts which bins are the empty (or non-empty) ones.

Then, because all positions are equiprobable, the desired probability is

$$P= \frac{r! \, S(m,r){n \choose r}}{n^m}=\frac{r! \, S(m,n-k){n \choose k}}{n^m}$$

Related Question