7
$\begingroup$

In 'An Introduction to Probability Theory and Applications' by W. Feller I encountered this apparently innocuous problem.

A throw of twelve dice can result in $6^{12}$ different outcomes, to all of which we attribute equal probabilities. The event that each face appears twice can occur in as many ways as twelve dice can be arranged in six groups of two each. Hence the probability of the event is $\displaystyle \frac{12!}{2^{6}6^{12}}=0.003438$.

The reasoning is that by doing that you're grouping two 1's, two 2's, ..., two 6's (each group using one partition in the multinomial) and the result is the number of different partitions that can be found with that particular characteristic. However, I had doubts about that answer. To understand better that problem, I did a simpler example with $4$ dice instead of $12$ (in this case, the event is the number of ways in which two faces appear twice).

Using the same result I get as the probability $\displaystyle \frac{4!}{2^{2}6^{4}}=$ 0.46 $0.0046$. Then, to see if that's true I ran a little simulation of this case in Mathematica:

dice = Table[Table[Random[Integer, {1, 6}], {i, 1, 4}], 
{j, 1, 1000000}]; i=0;
f[{a_, b_, c_, d_}] := Which[a === b && c === d && a != c, 
i++, a === c && b === d && a != b, 
i++, a === d && b === c && a != b, i++;];
Map[f, dice, {1}];

After $1000000$ steps I got $69687$ cases in which two faces appear twice. This is equivalent to a probability of $0.069687$. Far smaller than what I expected based on the calculation above.

Since this latter example is much more manageable than the one with twelve dice, I did the following

With four dice we have the following:

  1. Partition $r_{1}$ contains the first and second dice and partition $r_{2}$ contains the third and fourth dice.
  2. Partition $r_{1}$ contains the second and fourth dice and partition $r_{2}$ contains the first and fourth third.
  3. Partition $r_{1}$ contains the first and fourth dice and partition $r_{2}$ contains the second and third dice.
  4. Partition $r_{2}$ contains the first and second dice and partition $r_{1}$ contains the third and fourth dice.
  5. Partition $r_{2}$ contains the second and fourth dice and partition $r_{1}$ contains the first and fourth third.
  6. Partition $r_{2}$ contains the first and fourth dice and partition $r_{1}$ contains the second and third dice.

For each case, we can have $30$ outcomes in which two faces appear two times. For example, for the first case we have $1122, 1133, 1144, 1 155, 1166, 2211, 2233, 2244,2255, 2266,... 6611, 6622, 6633, 6644, 6655$. However, such outcomes are repeated twice (particularly, the outcomes of case 1 repeat the outcomes of case 4, etc). Therefore, the number of different outcomes which produce two faces appearing two times are $\frac{6}{2}6*5=90$. Since there are $6^{4}$ outcomes, we have a probability of $\frac{90}{6^{4}}=0.0694444$, which is the result that produces the simulation in Mathematica.

Is it wrong the first reasoning? If so, is there a general approach to use the multinomial coefficient to solve this kind of problems. For instance, it appears that this only happens for $r_{1}=r_{2}=r_{k}$. Otherwise, there are not repeated outcomes.

2 Answers 2

12

There are two things going on here. First, $\displaystyle \frac{4!}{2^{2}6^{4}}$ is about $0.0046$, not $0.46$.

Second, the problem described by Feller and your simplification to four dice are not the same problem. Feller's problem requires that each face appear twice. Your four-dice problem requires that $some$ two faces appear twice. There's only one way that Feller's event can be satisfied; namely, that each of 1, 2, 3, 4, 5, and 6 appear exactly twice. There are many more ways that some two faces could appear twice. For instance, you could have two 1's and two 2's, two 1's and two 3's, etc. In fact, there are $\binom{6}{2} = 15$ different ways to choose the two faces that will appear.

And that solves your problem. Taking the correct result from Feller, $\displaystyle \frac{4!}{2^{2}6^{4}} \approx 0.0046$, and multiplying it by the $15$ different ways to choose the faces gives $\displaystyle \frac{90}{6^4} \approx 0.0694444$.


With respect to your question about the multinomial coefficient, $\displaystyle \binom{n}{k_1, k_2, \ldots, k_m}$ calculates the number of ways to partition a set of $n$ items into $m$ groups with $k_1$ items in the first group, $k_2$ items in the second group, and so forth. So in Feller's problem $\displaystyle \binom{12}{2, 2, 2, 2, 2, 2}$ is calculating the number of ways to put two dice in the 1's group, two dice in the 2's group, and so forth.

In the four-dice problem you describe, you haven't specified a particular partition of dice into groups; there are several partitions that will satisfy "two faces appearing twice." So, in the four-dice problem, $\displaystyle \binom{4}{2, 2}$ counts the number of ways to put two dice in a 1's group and two dice in a 2's group. It also counts the number of ways to put two dice in a 1's group and two dice in a 3's group, and it counts the number of ways to put two dice in a 1's group and two dice in a 4's group, and so forth. So to calculate the total number of ways of obtaining "two faces appearing twice" you need to multiply $\displaystyle \binom{4}{2, 2}$ by the number of ways to pick two of the faces out of six possible faces, which is $\binom{6}{2}$. Then you mutiply by $\frac{1}{6^4}$ to get the probability you want.

If you want a general answer, the probability of throwing $n$ $d$-sided dice and having exactly $m$ faces appear $\frac{n}{m}$ times would be $$\binom{n}{m} \frac{n!}{((\frac{n}{m})!)^m d^n} .$$

  • 0
    Yes, I'm correcting it, indeed is $0.0046$. I know there are two different problems (the one from Feller's book and the other with four dice). Thanks for reminding me the 15 different ways to choose the two faces. One more thing: Obviously, the multinomial procedure doesn't take into account twice each outcome since it gives the correct probability. However, from the partitions I have, it seems that way (since there are $6$ ways to partition in subpopulations of $2$ the four elements). Can you clarify what are doing the multinomial coefficients in any case (with $12$ or $4$ elements)?2010-11-19
  • 0
    @Robert Smith: Sure. Let me think about it some, and I'll get back to you.2010-11-19
  • 0
    @Mike: Thank you very much.2010-11-19
  • 0
    @Mike: Having read your explanation I think I get why it works. Let me re-explain this in a different manner: We want to know how many different ways to get two faces appearing twice for four dice. The sample space is $\{11,22,33,44,55,66\}$ where each point reflects the result of a pair of dice. The possible outcomes for four dice (that is, getting two faces appearing twice) can be obtained by calculating $\displaystyle \binom{6}{2}$. However, binomial coefficients don't recognize differences of order in subsets (for example, $\{11,22\}$ and $\{22,11\}$ are counted as one outcome).2010-11-20
  • 0
    Then, we need to take into account those differences. We use the multinomial coefficients to produce the number of different ways, in this case, to partition a set of $4$ elements into $2$ groups. These are all the arrangements in which a certain outcome can appear. Nevertheless, multinomial coefficients are sensitive to the order of the partitions, therefore, it will repeat the outcomes twice. Since the binomial coefficient doesn't take into account half of the outcomes and the multinomial coefficient account for the double of the arrangements of the dice.2010-11-20
  • 0
    The product will result in exactly what we needed.2010-11-20
  • 0
    @Robert Smith: Right, except that multinomial coefficients aren't sensitive to the order of the partitions, either. The 2's in the denominator with the multinomial coefficient are there for another reason. The multinomial coefficient numerator $n!$ is a number of permutations, and so it counts putting die A and then die B into the 1's group as a different permutation from putting die B and then die A into the 1's group. To fix that (so that these are considered the same in the final accounting) you have to divide by $2! = 2$.2010-11-20
  • 0
    @Mike: I think multinomial coefficients are sensitive to the order of the partitions (I just hope we both have the same concept of 'partition'). Feller call them 'subpopulations' and partitions are the subsets of the populations: 'Note that the order of the subpopulations is essential in the sense that $r_{1}=2$, $r_{2}=3$ and $r_{1}=3$, $r_{2}=2$ represent different partitions; however, no attention is paid to the order within the groups.' This last statement is what you mean in your comment, right?2010-11-20
  • 0
    @Robert: Feller means that the partitions $\{111,22\}$ and $\{11,222\}$ are counted as different, not that $\{111,22\}$ and $\{22,111\}$ are counted as different. The multinomial coefficient really does consider $\{11,22\}$ and $\{22,11\}$ to be the same partition.2010-11-22
  • 0
    @Mike: Sure, $\{11,22\}$ and $\{22,11\}$ are considered the same partition, but take $\frac{4!}{2!2!}=6$. As I described in the original post, one of those $6$ ways to arrange four elements is $r_{1}$ containing the first and the second element, $r_{2}$ the third and fourth element. Another way would be $r_{1}$ containing the third and fourth element, $r_{2}$ the first and second element. Those are counted differently (in that way, you obtain $6$ partitions, not only $3$.2010-11-22
  • 0
    @Robert Smith: Agreed. I think the confusion is that we're using "partition" in different senses (as you indicated a few comments ago).2010-11-22
  • 0
    @Mike: Yes, I think I'm going to check that. It's very confusing.2010-11-22
  • 0
    How if the question is: **If we rolled an infinite number of dice at the same time, what would be the chance of getting exactly the same number of ones, twos, threes, fours, fives, and sixes?** Can we use your general formula to answer the question?2014-07-01
3

The case of four dice is not so hard. You require XXYY in some order, where X != Y. So let the first throw be X. Then there are three possibilities: XXYY, XYXY, and XYYX. Each has probability 1/6 x 5/6 x 1/6 = 5/216. So we get 5/72, which is about 0.0694. This agrees very well with your simulation!
The question is, where did you go wrong in your calculation? You calculated the probability of a specific XXYY -- say, two ones and two fives. Now you have to multiply by the number of such (X,Y) pairs, which is 15. And 15 x 4! / (2^2 x 6^4) is 5/72.

  • 0
    Yes, thanks to Mike Spivey I recognized that mistake. 1+ for your interest. Thanks Tony.2010-11-19