1
$\begingroup$

If I uniformly distribute $n$ balls into $k$ bags, I am trying to work out the distribution of the number of bags which are empty.

Now I had thought that I could use that each bag has $\text{Binomial}(n, \frac{1}{k})$ balls and use this but these distributions are not independent so this doesn't work.

Any help will be greatly appreciated.

$\endgroup$
  • $\begingroup$ How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag? $\endgroup$ – Peter Shor Mar 25 at 11:38
1
$\begingroup$

Define $P_k^n(m)$ as the probability, that there will be $m$ empty bags after $n$ balls were thrown into $k$ bags. Now, suppose, you have $k$ bags total and have already thrown $n - 1$ balls, and it resulted in $m$ bags remaining empty. Then, after the next ball is thrown, $m$ bags remain empty with probability $\frac{k - m}{k}$ and the number of empty bags will become $m - 1$ is $\frac{m}{k}$. So we have the following recurrence, that is sufficient to define all probabilities you search:

$$P_k^n(m) = \frac{k - m}{k}P_k^{n - 1}(m) + \frac{m}{k}P_k^{n-1}(m + 1)$$ $$P_k^0(k) = 1$$ $$P_k^0(m) = 0, \text{ if } m \neq k$$

$\endgroup$
0
$\begingroup$

It is also possible to get the following "closed form" for this distribution:

$$ \bbox[#EEE,6px,border:1.5px solid black]{\mathbb P\big(\text{# empty bags }=m\big)=\sum_{i=m}^k(-1)^{i-m}\binom{i}m\binom{k}{i}\left(1-{i\over k}\right)^n.} $$ This follows from the generalized inclusion exclusion principle. See Generalised inclusion-exclusion principle.

$\endgroup$

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.