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.

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.

share|improve this question

2 Answers 2

up vote 10 down vote accepted

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

share|improve this answer
    
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)? –  Robert Smith Nov 19 '10 at 21:41
    
@Robert Smith: Sure. Let me think about it some, and I'll get back to you. –  Mike Spivey Nov 19 '10 at 21:42
    
@Mike: Thank you very much. –  Robert Smith Nov 19 '10 at 21:45
    
@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). –  Robert Smith Nov 20 '10 at 5:41
    
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. –  Robert Smith Nov 20 '10 at 5:41

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.

share|improve this answer
    
Yes, thanks to Mike Spivey I recognized that mistake. 1+ for your interest. Thanks Tony. –  Robert Smith Nov 19 '10 at 21:47

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.