3
$\begingroup$

I understand that if you wanted to compute the probability of rolling a specific three of a kind or more (getting three or more $1$s for example) then you would just calculate $$\sum_{k=0}^3(5^k){6\choose 6-k}\over 6^6$$ but I am not so sure how you would go about calculating the probability for any value to appear three or more times in a roll of six dice. Simply multiplying the total outcomes for obtaining three or more of a specific value is obviously not correct because you would count outcomes such as $(1,1,1,2,2,2)$ once for getting three $1$s and again for getting three $2$s.

Is there a general formula or method one can use to obtain the answer to not only the dice scenario, but any scenario where $P(X\ge x)$ for $X$ denoting the maximum amount of times any value appears in a string of $m$ values generated from $n$ different values?

Thanks in advance, and sorry if my wording is bad. I'm still not entirely sure of the best way to word the last part.

$\endgroup$
  • 5
    $\begingroup$ For the question in the title, you can bypass the issue you correctly noticed using inclusion-exclusion, giving $\dfrac{6\cdot (5^3\binom{6}{3}+5^2\binom{6}{2}+5^1\binom{6}{1}+1)-\binom{6}{2}\binom{6}{3}}{6^6}$ $\endgroup$ – JMoravitz Feb 10 '19 at 2:44
  • $\begingroup$ @JMoravitz Thanks for the reply and solution, I was just unsure of how I would count the terms that would be over counted so I could remove them. $\endgroup$ – S. Burc Feb 10 '19 at 17:38
4
$\begingroup$

There's more than one way. What's best depends on the relative sizes of $m$, $n$, and $x$.

First, we can go "forward" - enumerate all ways to have three or more of a kind, all ways to have three or more of two kinds, and so on, then run inclusion-exclusion. As noted in the comment by @JMoravitz, this works pretty well for your example of $x=3,m=n=6$.
For a particular $k$, there are $\binom{6}{3}\cdot (6-1)^3$ ways to have three of $k$, $\binom{6}{4}\cdot (6-1)^2$ ways to have four of $k$, $\binom{6}{5}\cdot (6-1)$ ways to have five of $k$, and $\binom{6}{6}$ ways to have six of $k$. Multiply by $6$ to get a total of $$6\left(\binom{6}{3}\cdot 5^3+\binom{6}{4}\cdot 5^2+\binom{6}{5}\cdot 5^1+\binom{6}{6}\right)$$ ways. But, of course, this is an overcount. We can have three each of two different kinds, in $\binom{6}{3}$ ways to choose which three are the "first" kind and $\binom{6}{2}$ pairs of kinds. These were counted twice by the preceding, so we subtract them off to get $$6\left(\binom{6}{3}\cdot 5^3+\binom{6}{4}\cdot 5^2+\binom{6}{5}\cdot 5^1+\binom{6}{6}\right)-\binom{6}{2}\cdot\binom{6}{3}$$ $$= 6(20\cdot 125+15\cdot 25+6\cdot 5+1)-15\cdot 20 = 17136$$ ways. Divide by $6^6=46656$ for the probability (about $0.367$).

Of course, as we increase $m$ for fixed $n$ and $x$, eventually we reach a point where that $x$ of a kind is certain (Pigeonhole principle). If we're close to that point, the forward count will be horrible - but there's an alternative. We can count the ways to avoid any instances of $x$ of a kind, and subtract the resulting probability from $1$. I'll demonstrate this backward count for the same example:

To avoid three of a kind, we must have between zero and 2 of each of the six kinds. I'll enumerate the possible ways to split $6$ into a sum of six terms each between zero and $2$: $2+2+2+0+0+0$, $2+2+1+1+0+0$, $2+1+1+1+1+0$, $1+1+1+1+1+1$.
For $2+2+2+0+0+0$, we have $\binom{6}{3}$ ways to choose which three numbers on the die show up, then $\binom{6}{2,2,2}=\binom{6}{2}\binom{4}{2}$ ways to choose which rolls each number gets.
For $2+2+1+1+0+0$, we have $\binom{6}{2,2,2}$ ways to choose which numbers are represented to each level, then $\binom{6}{2,2,1,1}$ ways to choose the rolls.
For $2+1+1+1+1+0$, we have $\binom{6}{1,4,1}$ ways to choose the numbers and $\binom{6}{2,1,1,1,1}$ ways to choose the rolls.
For $1+1+1+1+1+1$, we have one way to choose the numbers and $\binom{6}{1,1,1,1,1,1}=6!$ ways to choose the rolls.
Summing those up, that's $$20\cdot 90+90\cdot 180+30\cdot 360+1\cdot 720 = 29520$$ ways to avoid three of a kind. The probability we seek is $$1-\frac{29520}{46656}=\frac{17136}{46656}\approx 0.367$$ This backwards count never really goes too bad - the example here is a "worst" case of having the most possible ways to split $m$ - but it's particularly efficient when $m$ is close to $n(x-1)$, and it's instant when we're in the case $m > n(x-1)$ and at least one instance of $x$ of a kind is certain.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for this detailed response! If I am understanding it correctly then I should be able to calculate the probability for $x=3, m=6$, and $n=124$ by doing $${124 \cdot \left({6\choose 3}\cdot 123^3+{6\choose 4}\cdot 123^2+{6\choose 5}\cdot 123^1+{6\choose 6}\right)-{124\choose 2}\cdot {6\choose3}}\over 124^6$$ Since there are $124\choose2$ pairs of kinds and $6\choose 3$ ways to arrange the first kind. I hope I am understanding the 'ways to arrange the first kind' correctly as different ways of ordering $(x,x,x,y,y,y)$. $\endgroup$ – S. Burc Feb 10 '19 at 18:39
  • 1
    $\begingroup$ Yes, that's correct. $\endgroup$ – jmerry Feb 10 '19 at 20:00
  • $\begingroup$ Okay, thank you very much. $\endgroup$ – S. Burc Feb 10 '19 at 20:08

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.