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.

A pair of dice is rolled repeatedly until each outcome (2 through 12) has occurred at least once. What is the expected number of rolls necessary for this to occur?

Notes: This is not very deep conceptually, but because of the unequal probabilities for the outcomes, it seems that the calculations involved are terribly messy. It must have been done already (dice have been studied for centuries!) but I can't find a discussion in any book, or on line. Can anybody give a reference?

share|improve this question

2 Answers 2

This is the coupon collectors problem with unequal probabilities. There is a treatment of this problem in Example 5.17 of the 10th edition of Introduction to Probability Models by Sheldon Ross (page 322). He solves the problem by embedding it into a Poisson process. Anyway, the answer is

$$ E[T]=\int_0^\infty \left(1-\prod_{j=1}^m (1-e^{-p_j t})\right) dt, $$

when there are $m$ events with probability $p_j, j=1, \dots, m$ of occurring.

In your particular problem with two fair dice, my calculations give

$$E[T] = {769767316159\over 12574325400} = 61.2173.$$

share|improve this answer
4  
+1: I was typing up exactly the same answer when you posted :) although I was using the following paper by Flajolet, Gardy, and Thimonier: algo.inria.fr/flajolet/Publications/FlGaTh92.pdf –  Mike Spivey Mar 7 '11 at 18:17
    
@Mike Yeah, I was pretty fast on the draw. I happen to be teaching this section in my probability class. Thanks for the reference, it looks interesting! –  Byron Schmuland Mar 7 '11 at 18:22

Suppose the probabilities are $p_i$. For each set $S$, the probability that in the first $n$ terms we have only seen throws from $S$ is $$ p_S^n, \quad p_S \triangleq \sum_{i \in S} p_i. $$ The probability that we have not seen all outcomes by the $n$th throw is $$ r_n = \sum_{S \neq \emptyset} (-1)^{|S|+1} p_{\overline{S}}^n. $$ The required expectation is $$ E = \sum_{n \geq 1} r_n. $$ Changing the order of summation, the summand corresponding to $S$ contributes to the sum $$ (-1)^{|S|+1} \sum_{n \geq 1} p_{\overline{S}}^n = \frac{(-1)^{|S|+1} p_{\overline{S}}}{p_S}. $$ So we get the formula $$ E = \sum_{S \neq \emptyset} (-1)^{|S|+1} \left(\frac{1}{p_S} - 1 \right) = \sum_{S \neq \emptyset} \frac{(-1)^{|S|+1}}{p_S} - 1. $$ You can now in principle plug in the values of the dice and get the result. Since there are $11$ outcomes, you need to sum $2^{11} = 2048$ reciprocals (including the final $-1$).

share|improve this answer
    
+1: This looks like it might be Equation 14b in the paper I mention under Byron's answer. –  Mike Spivey Mar 7 '11 at 18:33

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.