Assume that there are $n$ balls (numbered from $1$ to $n$) and $n$ urns (numbered from $1$ to $n$). At the beginning no ball is placed in any urn. Balls are randomly thrown into urns: Each ball is thrown at each urn with probability $1/n$.

What is the probability that there are exactly $k$ empty urns?

  • $\begingroup$ The labels for the balls and urns, incidentally, have no effect on this problem. $\endgroup$ – Thomas Andrews Apr 4 '13 at 15:23
  • $\begingroup$ @Thomas: They do. For $n=3$, with urns and balls labelled, the probability of no empty urn is $\frac29$. With urns labelled and balls unlabelled, it’s $\frac1{10}$; with neither urns nor balls labelled, it’s $\frac13$. $\endgroup$ – Brian M. Scott Apr 4 '13 at 19:14
  • $\begingroup$ That can't be true, @BrianM.Scott. That's only true if you ignore the conditions of the problem and treat results "2,1,0" and "1,1,1" as equal probability. $\endgroup$ – Thomas Andrews Apr 4 '13 at 19:17
  • $\begingroup$ @Thomas: But if you ignore the labels, you are treating those as having equal probability. That’s precisely why you can’t ignore the labels, and why Ross’s solution doesn’t work. $\endgroup$ – Brian M. Scott Apr 4 '13 at 19:18
  • $\begingroup$ @BrianM.Scott, which part of the condition: "Balls are randomly thrown into urns: Each ball is thrown at each urn with probability $1/n$" am I missing? The result set is smaller - there are not $n^n$ different results - but each result is not equally likely. $\endgroup$ – Thomas Andrews Apr 4 '13 at 19:22
  1. Choose $n-k$ urns that won't be empty.
  2. Group the $n$ balls into $n-k$ non-empty sets.
  3. Distribute groups of balls into the designated urns.

These 3 steps explain the three factors in this expression: $$\mathbb{P}(\text{exactly } k \text{ urns are empty})={{n\choose n-k}{n \brace n-k}(n-k)!\over n^n}.$$

The notation ${n \brace n-k}$ refers to Stirling numbers of the second kind.

  • $\begingroup$ Excellent! Thanks. $\endgroup$ – Emre Per Apr 4 '13 at 22:17
  • $\begingroup$ @EmrePer No problem! I love throwing balls in urns :) $\endgroup$ – user940 Apr 4 '13 at 22:18
  • $\begingroup$ If you love balls and urns, can you have a look at the other question I posted (sequential allocation of balls into urns) :) I think it is a complicated one. I would appreciate your thoughts on that one. That is the original question that I am interested in. This question seems to be a small step in solving the other question. $\endgroup$ – Emre Per Apr 4 '13 at 22:26

Hint: how many ways are there to choose the $k$ empty urns? How many ways to distribute the balls into the $n-k$ urns such that each urn gets at least one ball? For the second, think stars and bars.

  • $\begingroup$ My problem is that I can not compute How many ways to distribute the balls into the n−k urns such that each urn gets at least one ball since balls are also distinguishable? That is, (Ball 1, Ball 2 in urn 1, ball 3 in urn 2) is different than (Ball 1, Ball 3 in urn 1, ball 2 in urn 2). I see that answer will be: There are $n^{n}$ ways to put $n$ balls to $n$ urns. There are $\binom{n}{k}$ ways to choose $k$ empty urns. We want to place $n$ balls into $n-k$ urns which can be done in $x$ ways. Hence, the result is \ \frac{1}{n^{n}}\binom{n}{k}x \ $\endgroup$ – Emre Per Apr 4 '13 at 16:03
  • $\begingroup$ @EmrePer: As Thomas Andrews comments, you can ignore the labels on the balls (and urns) if you want the probability of a given number of empties. $\endgroup$ – Ross Millikan Apr 4 '13 at 16:08
  • $\begingroup$ Well, actually, I am confused now. Let's consider $n=3$. Assume there are no labels. Then, there are 3 ways to allocate balls: 3+0+0, 2+1+0, 1+1+1. Then, the probability of emptiness for each $k$ is $1/3$? But, this is not true in labeled version. What am I missing? $\endgroup$ – Emre Per Apr 4 '13 at 16:39
  • $\begingroup$ @EmrePer: You’re not missing anything: the labels matter. $\endgroup$ – Brian M. Scott Apr 4 '13 at 19:14
  • $\begingroup$ You are missing that the 3 ways are not equally likely. 3+ 0+0 has p=1/9, 2+1+0 has p=6/9 and 1+1+1 has p=2/9. The labels DO NOT matter. The logic is, for $\endgroup$ – Dale M Apr 4 '13 at 22:48

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.