Probability that exactly k bins are empty, given m balls and n bins?

Question

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.

Answer 1

(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}$$

Answer 2

The problem is equivalent to throwing an n sided die m times, with only n-k distinct outcomes

You can do it in three steps, using Stirling numbers of the second kind

I will do it for a small numerical example, throwing a $6$ sided die $8$ times and getting only $4$ distinct results, (i.e. 2 "bins" remain unfilled.) You should be able to generalise it.

1. Choose which of the $4$ "bins" are to be filled : $\binom64 = 15$

2. Using Stirling numbers of the $2nd$ kind, partition the $8$ "balls" into $4$ non-empty groups, ${8\brace 4}= 1701$

3. Assign the $4$ values from step 1 to the groups from step 2, $\;\;4! = 24$

Then $$\mathbb{P}(X=4)={\displaystyle{6\choose 4}\, {8\brace 4} \, 4!\over { 6^8}}.$$

Do note that the formula has been derived using the bins filled. Though $\binom64 = \binom62$, the latter carries the risk of using the wrong Stirling number.

Answer 3

I've searched for an understandable answer...

You want $P(k|n,m)$ which is the probability that when $m$ balls are thrown into $n$ bins randomly, with each throw being independent of others, $k$ bins will remain empty.

Let us dispose of some easy special cases right away. Obviously number of empty bins cannot be greater than the total number of bins, so for $k>n$, $P(k|n,m)=0$. So in what follows we assume $k\leq n$.

Number of empty bins equals total number of bins only if no balls have been thrown, i.e. $P(k=n|n,m=0)=1$ and $P(k=n|n,m>0)=0$. So in what follows we assume $k<n$ and $m>0$.

If $k$ bins are to remain empty then the remaining $(n-k)$ bins must have at least one ball each. Therefore if less than $n-k$ balls have been thrown then the number of empty bins will be greater than $k$. That is, $P(k|n,m)=0$ for $m<n-k$. So in what follows we assume $m\geq n-k$.

So finally we are down to the non-trivial case: $m>0$ (at least one ball has been thrown), $k<n$ (number of empty bins is less than the total number of bins), and $m\geq n-k>0$ (sufficient number of balls have been thrown to make the problem non-trivial).

If exactly $k$ bins are to remain empty then the rest of $n-k$ bins must be filled. Let us a take a particular set of $n-k$ filled bins and label them from numbers from $1$ through to $n-k$. The probability that any throw lands in one these bins is $(n-k)/n=1-k/n$. Since the throws are independent, the probability that all $m$ throws land up in these bins is $(1-k/n)^m$. The number of ways of choosing $n-k$ bins is $C_{n-k}^n=C_k^n$. Therefore the required probability is $P(k|n,m)=C_k^n (1-k/n)^m$ for $k<n$ and $m\geq n-k$.

Answer 4

$\underline{Another\;approach\;for\;the\;numerical\;in\;my\;previous\;answer}$

Throw a six-sided die $8$ times, and get exactly $4$ faces showing up.

There are $5$ possible patterns:
$5-1-1-1\;of\;a\;kind$
$4-2-1-1\;of\;a\;kind$
$3-3-1-1\;of\;a\;kind$
$3-2-2-1\;of\;a\;kind$
$2-2-2-2\;of\;a\;kind$

For each, you can use the formula [Choose die faces to show] $\times\;$[ Permute], e.g. for the first pattern,

$5-1-1-1\;of\;a\;kind:$
$\left[\binom61\binom53\;\text{Choose die faces to show }\right]\times\left[\frac{8!}{5!1!1!1!}\text{Permute}\right]$

which can be more conveniently expressed as the product of two multinomials, $\binom{6}{1,3,2}\binom{8}{5,1,1,1}$

Similarly, for $4-2-1-1\;of\;a\;kind \;\;\binom{6}{1,1,2,2}\binom{8}{4,2,1,1}$

Work out for all $5$ patterns, add up and divide by $6^8$

---