1
$\begingroup$

There is a question and answer that almost answers my question: Calculating the probability of getting a specific set of dice from a single roll

In that link the number of dice being rolled is the same as the number in the specific set that we are trying to match. However, what if we want to add more dice?

For example, suppose we want to get the outcome {2,4,5}.

How do we calculate the probability of getting this set by rolling 4 dice once? How about 5 dice, 6 dice, ... N dice?

Asked another way, how do we calculate the probability that the desired outcome above {2,4,5} is a subset of 4 dice rolled simultaneously? 5 rolled dice? N rolled dice?

For example, all of the following rolled outcomes would be considered a 'match' to the above specified set:

  • {1,2,4,5}, {2,2,4,5}, {2,4,5,6} (4 dice)
  • {2,2,4,5,6}, {1,2,3,4,5}, {2,3,4,5,5} (5 dice)
  • {2,2,4,4,5,5}, {1,2,3,4,5,6} (6 dice)

The desired outcome must appear at least once but could appear multiple times.

Further examples that would not be considered a match:

  • {1,2,3,5}, {2,2,4,6}, {2,4,6,6} (4 dice)
  • {2,2,3,4,6}, {1,2,3,4,6}, {1,3,4,5,5} (5 dice)
  • {1,3,4,4,5,5}, {1,2,3,4,6,6} (6 dice)

Your help is greatly appreciated!

$\endgroup$
  • $\begingroup$ Do want one 2, one 4, and one 5? Or with four dice would 2245 be OK. Also does order matter? $\endgroup$ – BruceET Feb 11 '17 at 17:39
  • $\begingroup$ You include $\{1,2,3,4,5,5\}$ in the list of "further examples that would not be considered a match" which I believe is included in error. $\endgroup$ – JMoravitz Feb 11 '17 at 18:13
  • $\begingroup$ JMoravitz, you are correct that is a valid match. My mistake. $\endgroup$ – MJActuary Feb 11 '17 at 19:21
  • $\begingroup$ BruceET - Order does not matter as we are rolling a group of dice at once, so 2245 would be a match for a roll of four dice. $\endgroup$ – MJActuary Feb 11 '17 at 19:22
0
$\begingroup$

There are a number of approaches, some may be more helpful for small values of $N$ while others may be more helpful for large values of $N$. I will go over three such approaches below. In all of these methods, the underlying principle that we are working with relies on the fact that the dice are fair and each sequence of length $N$ using characters $\{1,2,3,4,5,6\}$ is equally likely to occur. The methods may be modified slightly to account for unfair dice by putting appropriate weights on each specific calculation.

In each of these examples, I will look specifically at the example of getting each of $\{2,4,5\}$ at least once each in the roll of $N$ fair dice.


Direct approach via Counting:

Here, we break into cases based on how much repetition there is, how many of the dice show desired numbers and of what kind. We count how many sequences satisfy the property, total them up, and divide by $6^N$ which is the number of possible equally likely sequences we could have seen for the dice rolls.

Four dice:

  • Each desired number occurs exactly once: The numbers appearing are $\{2,4,5,X\}$ where $X$ is not any of $2,4,5$ There are $4!$ arrangements of $2,4,5,X$ and there are $3$ choices for the value of $X$. There are then $4!\cdot 3$ possible sequences in this case

  • One of the desired numbers occurs twice: Pick which number appeared twice and pick the order in which they occur. There are $\binom{4}{2,1,1}\cdot 3 = \frac{4!}{2!1!1!}\cdot 3$ possible sequences in this case

The probability is then $(4!+4!/2)\cdot 3 / (6^4)$

For more dice, this approach becomes incredibly tedious, for example in the six-dice case we must consider each of the cases:

  • Each desired die occurs exactly once: $\binom{6}{1,1,1,3}\cdot 3^3$
  • One desired die occurs twice, the others once: $\binom{6}{2,1,1,2}\cdot 3^2\cdot 3$
  • Two desired dice occur twice, the other once: $\binom{6}{2,2,1,1}\cdot 3\cdot 3$
  • One desired die occurs thrice, the others once: $\binom{6}{3,1,1,1}\cdot 3\cdot 3$
  • One desired die occurs thrice, another occurs twice, and the other once: $\binom{6}{3,2,1}\cdot 3\cdot 2$
  • One desired die occurs four times, the others once: $\binom{6}{4,1,1}\cdot 3$

This clearly is infeasible to work towards a clean solution for arbitrary $N$ as there are so many cases to consider.


Direct via Generating Functions:

Consider the generating function $(a+b+c+d+e+f)^N$ and add up the coefficients of every term with the exponents on each of $b,d,e$ each greater than or equal to $1$. For example in $(a+b+c+d+e+f)^4$ we would add up the coefficients of the terms $abde, b^2de, bcde, bd^2e, bde^2$ and $bdef$. This is relatively easy for a computer to do and gives a method to a solution, but again is rather frustrating to actually get a value for.

Even better yet, since we only care about the exponents of $b,d$ and $e$, the generating function could be replaced with $(1+b+1+d+e+f)^N$, i.e. $(b+d+e+3)^N$, limiting the total amount of computation necessary. You may adjust the generating function accordingly based on the specific example you are trying to calculate the probability for, as well as the desired minimum exponents on each appearing term.

Once you have found the total of the coefficients of the corresponding valid terms, divide the total by $6^N$ to get your probability.


Indirectly via Inclusion-Exclusion

Consider the events: $B,D,E$ corresponding to a $2$ not appearing, a $4$ not appearing, and a $5$ not appearing respectively. Counting the number of sequences in which all three of these do not occur simultaneously would correspond to finding the size of the set $|B^c\cap D^c\cap E^c|$ which by De'Morgans corresponds to finding $|\Omega \setminus (B\cup D\cup E)|$ which by inclusion-exclusion becomes $|\Omega|-|B|-|D|-|E|+|B\cap D|+|B\cap E|+|D\cap E|-|B\cap D\cap E|$, each term of which is relatively easy to calculate.

$|\Omega|$ is just the number of sequences of dice where we don't care about any other conditions and is of the size $6^N$.

$|B|,|D|,|E|$ each correspond to the number of sequences of dice where their respective number never occurs and are each of the size $5^N$.

$|B\cap D|,|B\cap E|,$ and $|D\cap E|$ each correspond to the number of sequences of dice where the both of their respective numbers never occur and are each of the size $4^N$.

Finally, $|B\cap D\cap E|$ is the number of sequences where none of the three numbers occur and is of the size $3^N$. Each of these calculations of course can be seen via direct application of the multiplication principle.

We have then the probability that at least one of each occurs is $\dfrac{6^N-3\cdot 5^N+3\cdot 4^N-3^N}{6^N}$

This of course is much easier to implement for this specific example. This will become harder to implement however if you have repetition in the desired set, say for example trying to calculate the probability of rolling at least three $3$'s and at least four $4$'s out of $20$ dice, inclusion-exclusion isn't necessarily going to be any more useful than the others as there is again going to be a great deal of case-work necessary in the computations.

$\endgroup$
  • $\begingroup$ Thank you so much for providing three clear examples. Greatly appreciated. $\endgroup$ – MJActuary Feb 11 '17 at 19:27

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.