2
$\begingroup$

Question:Throw at random 10 balls into 4 boxes. What is the probability that exactly 2 boxes remain empty?

My Solution: Using the stars and bars method, the boxes and balls can be thought as $0$ and | e.g. one configuration would be $$ 000000|00|0|0 $$ which would represent 6 balls in the first box etc. Thus the total number of configurations would be $\binom{13}{3}=286.$

There are $\binom{4}{2}$ to have 2 out of the 4 boxes empty, then to ensure the balls are put into only the other two boxes you place 1 ball into the other two boxes and then distribute the remaining 8 balls into the 2 boxes, which, using the same method as above, gives $\binom{9}{1}$ ways. Therefore there are $\binom{4}{2}*\binom{9}{1}=54$ ways of having exactly two boxes empty, giving a probability of $54/286\approx0.189.$

I did a simulation in MATLAB to confirm the answer, to find that I get a probability of $\approx0.005$, way off my answer. I can't see why my code and my solution above disagree so I'll post my code Here

$\endgroup$
  • $\begingroup$ We may temporarily assume that each ball is distinguishable in order to make computations easier to explain. Presumably each ball has a uniform probability for going into each of the boxes independent of the other balls. Not all of the 286 arrangements will be equally likely. Take for example the arrangement where all balls go into the first box (occurs with probability $\frac{1}{4^{10}}$) as compared to the arrangement where five go into first and five go into second which occurs with probability $\frac{\binom{10}{5}}{4^{10}}$. $\endgroup$ – JMoravitz Aug 1 '16 at 3:19
  • $\begingroup$ As an aside, you correctly counted the number of arrangements of the balls where they are indistinct. If we knew ahead of time that all possible arrangements of indistinct balls were equally likely to occur, your answer would have been correct. This does not however accurately model the real life scenario where each ball is thrown separately and independently. $\endgroup$ – JMoravitz Aug 1 '16 at 3:35
  • $\begingroup$ Indeed: The "Stars and Bars" technique counts distinct outcomes; it does not guarantee that these will be equi-probable outcomes (and usually they are not). It should be used with extreme caution in probability calculations (mainly: it should not be used at all). $\endgroup$ – Graham Kemp Aug 1 '16 at 3:50
  • $\begingroup$ Intuitively speaking, it's fairly obvious 0.189 is much too high a number for 10 balls to be spread over two of the four boxes only. This basically means that running this experiment, on average (almost) 1 out of 5 times two of the four boxes would be empty! $\endgroup$ – Babyburger Aug 1 '16 at 5:08
5
$\begingroup$

Temporarily assume the balls are labelled. This allows us to look at the sample space $\{1,2,3,4\}^{10}$ of size $4^{10}$ which will happen to be equiprobable, allowing us to use counting methods. (the sample space of size $\binom{13}{3}=286$ where the balls are indistinct is not equiprobable and so we may not use elementary counting methods with this choice)

Break apart via multiplication principle.

  • Pick which two boxes are empty. $\binom{4}{2}$
  • Pick how the balls are arranged among the two non-empty boxes.
    • To do so, ignore the condition that they be non-empty: there are $2^{10}$ choices
    • Then, remove the "bad" arrangements, where all ten are in the same box leaving the other empty. There are $2$ bad arrangements
    • This gives a total of $2^{10}-2$ ways to arrange among two boxes.

Applying multiplication principle then, there are $\binom{4}{2}(2^{10}-2)=6132$ ways to arrange the ten balls among the four boxes having exactly two boxes empty.

Dividing by the size of the sample space then, the probability is:

$$\frac{6132}{4^{10}}\approx 0.0058479$$

much more closely matching your simulation.

$\endgroup$
2
$\begingroup$

Generalizing (using urns instead of boxes, to make the variables a little easier to name):

How many ways are there to distribute $b$ unlabeled balls into $u$ urns such that exactly $k$ of those urns are empty?

Choose exactly $u-k$ urns that won’t be empty, group the $b$ balls into $u-k$ sets with at least $1$ ball in each group, and then count the number of ways to distribute those groups among the $u-k$ non-empty urns.

To get the probability, divide by $u^b$, since each of the $b$ balls can be allocated among any of the $u$ urns.

$$P(b, u, k) = \frac{\binom{u}{u-k}{b \brace u-k}(u-k)!}{u^b}$$

Where ${n \brace k}$ is a Stirling number of the second kind.

$$P(10,4,2) = \frac{6132}{4^{10}} = 0.0058479309...$$

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