3
$\begingroup$

This question was inspired by this question dealing with finding the probability of rolling a $7$ of a kind with $10$ dice.

Is there a general method for finding the chance of rolling a $k$ of a kind with $n$ $m$-sided dice when $k\leq n/2$? When $k>n/2$ the probability is found relatively easily with the Bernoulli distribution, but when $k\leq n/2$ there's the possibility that one may roll a second, or third, etc., $k$ of a kind with the other $n-k$ di(c)e. I don't see a clear way around this possible over counting.

Thanks!

  • 0
    @Tony K, I'm sorry if I was unclear. My definition of getting exactly $k$ of a kind, just means that there should be at least one $k$ of a kind of some sort. So yes, if I were looking for a three of a kind, I would consider three twos and four fives a $3$ of a kind of twos, but of course not a three of a kind of fives. Similarly, I would accept three twos and three fives as both a three of a kind of twos and a three of a kind of fives.2011-01-12

3 Answers 3

5

Let $A_i$ be the event that we obtain exactly $k$ $i$'s (assuming that the dice are labeled $1,2,3,\ldots,m$ on their sides). Now inclusion-exclusion gives

$P(A_1 \cup A_2 \cup \ldots \cup A_m) = \sum P(A_i) - \sum P( A_i \cap A_j) + \sum P(A_i \cap A_j \cap A_k ) - \cdots $

where the summations range over distinct $i,j,k,\ldots .$

We have

$P(A_i) = { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k} $

and

$P(A_i \cap A_j) = { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k} \cdot { n-k \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-2k} $

and

$P(A_i \cap A_j \cap A_k)$ $ = { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k} \cdot { n-k \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-2k} \cdot { n-2k \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-3k} $

and so on.

Simplifying these expressions, the probability that we get exactly $k$ of a number is given by

$P(A_1 \cup A_2 \cup \ldots \cup A_m) $

$ = { m \choose 1 } { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k} $

$ - { m \choose 2 } { n \choose k} { n-k \choose k} \left( \frac{1}{m} \right)^{2k} \left( 1 - \frac{1}{m} \right)^{2n-3k}$

$ + { m \choose 3} { n \choose k} { n-k \choose k} { n-2k \choose k} \left( \frac{1}{m} \right)^{3k} \left( 1 - \frac{1}{m} \right)^{3n-6k} - \cdots $

  • 0
    @yunone: I've just spotted your comment to Tony K in the question and I am happy that my interpretation o$f$ the question agrees with the question you want to ask.2011-01-12
1

Isn't this pretty straightforward? You pick the side that you want there are $m$ ways to do this. Then you are rolling $n$ dice and you want k dice to be a certain side of which there is a $(1/m)^k$ chance (if in a row) and then $((m-1)/m)^{(n-k)}$ for the remaining dice. You also need to account for different orders so you have $n$ choose $k$ choices for your dice on side k and these will determine the positions of your non-k sided dice. Putting everything together we get

$m \binom{n}{k} \frac{1}{m^k}\left(\frac{m-1}{m}\right)^{n-k}.$

Whoops, wasn't paying attention when I wrote this. Then we want to know the probability that none of the remaining (n-k) dice are a k of a kind. So we need to subtract away the probability that there exists a k of a kind in the spare dice. First we have (n-k) choose k pairs to examine and the probability that all k are not the same so once again we have to pick a side, but note that we can only pick (m-1) sides because we've already ensured that they are not one of the sides. Finally we get

$m \binom{n}{k} \frac{1}{m^k}\left(\frac{m-1}{m}\right)^{n-k}-(m-1)\binom{n-k}{k}\frac{1}{(m-1)^k}.$

I believe this is right, it certainly holds for the k>n/2 case.

  • 0
    It's definitely not correct though, it makes sense on a superficial level, but it's not right. I wrote up a quick program to run the simulation and also calculate my formula and it's not correct. Jennings answer is right I'm fairly sure though.2011-01-12
1

You can avoid the over-counting using the inclusion-exclusion principle.