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?


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

  • 7
    $\begingroup$ +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 $\endgroup$ Mar 7, 2011 at 18:17
  • $\begingroup$ @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! $\endgroup$
    – user940
    Mar 7, 2011 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$).

  • $\begingroup$ +1: This looks like it might be Equation 14b in the paper I mention under Byron's answer. $\endgroup$ Mar 7, 2011 at 18:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .