# Probability distribution of number of times required to roll all of a certain set of k numbers?

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.

-

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.

-
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

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.)

-
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