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.

Consider a 12-sided fair die. What is the distribution of the number T of rolls required to roll a 1, a 2, a 3, and a 4?

Taking inspiration from the Coupon Collector's Problem, I believe that the expected number of rolls to achieve the goal would be

$$E[T] = \sum\limits_{i=0}^3 \frac{12}{4-i} = 25$$

Similarly, the variance would be

$$Var[T] = \sum\limits_{i=0}^3 \frac{1-\frac{4-i}{12}}{(\frac{4-i}{12})^2} = 180$$

But applying Chebyshev here does not yield very useful bounds. My question is therefore, how would you compute, for example, $P(T=16)$ or $P(T<30)$?

Ideally this could be generalized to a set of k required numbers, not just 4 as in the example.

share|improve this question
add comment

2 Answers

up vote 0 down vote accepted

Personally I would call $P(n,b,k,j)$ the probability that after rolling $n$ dice with $b$ sides, $j$ of the target $k$ sides had been found, with the formula

$$P(n+1,b,k,j)= \frac{b-k+j}{b} P(n,b,k,j) + \frac{k+1-j}{b} P(n,b,k,j-1)$$

starting from $P(0,b,k,j)=0$ for $j \not = 0$ and $P(0,b,k,0)=1$.

Then $$\Pr(T \le t) = P(t,b,k,k)$$ and $$\Pr(T = t) = P(t,b,k,k)-P(t-1,b,k,k).$$

So in your example it is not difficult to calculate $\Pr(T = 16) \approx 0.0380722$ and $\Pr(T \le 30) \approx 0.7305294$. Your expected value of $T$ and variance appear to be correct.

share|improve this answer
    
Thanks for the response. A recursive definition is a good idea. I feel though that in your response, in the recurrence relation, one of the P's needs to have a j-1. –  vote539 Dec 27 '12 at 13:31
    
@vote539: your final point is correct and I will edit –  Henry Dec 27 '12 at 13:48
    
Thanks for the clarification! The results yielded by your solution match those yielded by a simulation of the dice rolls. A note to anyone who wants to implement this: the recursion stack grows very quickly, so it is necessary to use dynamic programming; that is, cache the results of the P function and only perform the computation when there is no cached value. –  vote539 Dec 27 '12 at 19:46
    
Or you could use a spreadsheet –  Henry Dec 27 '12 at 23:26
add comment

I think it's the sum of four different geometric distributions.

For example, you start off and you haven't rolled any of the numbers. The probability of rolling one of them is 4/12 so you start a geometric distribution with that parameter. Then you suddenly roll one of them. Now you need to roll one of the other three, each roll has a probability of 3/12 of getting one of them, so it's another geometric distribution.

By this logic I think T ~ Geo(4/12) + Geo(3/12) + Geo(2/12) + Geo(1/12) which of course is probably some hideous ditribution define in terms of convolutions (or you know, could miraculously be nice and of closed-form, I don't know what.)

share|improve this answer
    
This is sort-of what I was thinking, but what are the next steps to get to the point when you can actually compute the probability densities? –  vote539 Dec 27 '12 at 10:01
add comment

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.