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.

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!

share|improve this question
    
You have to define what you mean here, I think. Suppose you want exactly three of a kind in ten rolls. Presumably you would reject a result of three twos and four fives, say. Would you also reject a result of three twos and three fives? –  TonyK Jan 12 '11 at 13:56
    
@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. –  yunone Jan 12 '11 at 14:50

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
This is based on my interpretation that the poster if after the probability that we get exactly $k$ of one number when $n$ $m$-sided dice are rolled. –  Derek Jennings Jan 12 '11 at 14:02
    
Thanks for this answer, Derek. I think this may be what I'm looking for. Based on a comment by Tony K, I'm afraid my definition of a $k$ of a kind may have been confusing. If I understand you correctly, if a roll was given where there were say $k$ twos and $k$ fives, you would accept this as both a $k$ of a kind of twos, as well as a $k$ of kind of fives, as opposed to outright rejecting it as either? And then of course your calculation uses IE to not overcount such a situation? –  yunone Jan 12 '11 at 14:56
    
@yunone: Yes, I would accept exactly $k$ twos and exactly $k$ fives appearing in the roll of the $n$ dice and, as you say, use IE not to overcount. –  Derek Jennings Jan 12 '11 at 18:05
    
@yunone: I've just spotted your comment to Tony K in the question and I am happy that my interpretation of the question agrees with the question you want to ask. –  Derek Jennings Jan 12 '11 at 18:22

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

share|improve this answer

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.

share|improve this answer
    
You are heading in the right direction of the inclusion-exclusion principle, but need to keep going in case k<n/3 and there are three sets of k and so on. –  Ross Millikan Jan 12 '11 at 13:57
    
Thank you for this response, Jacob. –  yunone Jan 12 '11 at 14:57
    
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. –  JSchlather Jan 12 '11 at 15:05

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.