5
$\begingroup$

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.

$\endgroup$
0

4 Answers 4

4
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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$


$\endgroup$
1
  • $\begingroup$ @Deep: As promised, I have added another approach. $\endgroup$ Dec 1, 2017 at 18:31
0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ This is not correct, and I am downvoting as it may mislead anyone who chances upon it. The probability that you are computing is that all these throws land up in one or other of "these bins", whereas the question requires that $all$ of "these bins" be occupied. $\endgroup$ Dec 1, 2017 at 15:01
  • $\begingroup$ I am shortly going to add a more elementary (albeit lengthier) approach to the numerical example in my original solution. $\endgroup$ Dec 1, 2017 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.