Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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>=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

share|improve this question
add comment

2 Answers 2

up vote 12 down vote accepted

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

share|improve this answer
    
Thanks. I like it - the question is simple but the expression for the answer is disappointing complicated — we define a concise notation to make maths beautiful again. –  Colonel Panic Aug 3 '12 at 15:47
    
@Colonel: But note this approximation to the result. –  joriki Oct 11 '12 at 23:27
add comment

To count the outcomes for this question, using inclusion-exclusion formula is correct, but $n$ choose $k$ and then multiplied by $k!$ is only correct if the question is asking that "each bin has only one ball". If n balls are thrown into $n$ bins, then, a simple answer is $n!$. So the question asking at least one ball is complicated. We have to write down each possible way and sum up each combination, just like another question asking about each day per week has at least one call. If we have exact numbers, we can count the numbers of outcomes, but here, it is better to ask at least one ball with the setting of $n$ balls thrown into $n$ bins.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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