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.

What is the expected number of times one must throw two fair dice before all numbers from 2 to 12 have appeared at least once?

share|improve this question
    
This sounds interesting. With one die its easy, see e.g. here: madandmoonly.com/doctormatt/mathematics/dice1.pdf p.9 –  vonjd May 31 '11 at 12:30
    
What do you mean by "expected". In other words, at what probability threshold do you draw the line - the probability of all numbers appearing approaches, but never hits 1. –  crasic May 31 '11 at 12:33
    
@crasic: You could reformulate it: On average, how many times must two 6-sided dice be rolled until all numbers from 2 to 12 appear at least once? –  vonjd May 31 '11 at 12:42
    
One approach would be to consider the probability transitions among states consisting of subsets of $\{2,...,12\}$ given by the chance of a new number appearing (given the previously obtained sums). This amounts to $2^{11} = 2048$ states to keep track of, easily reduced by half owing to symmetry, something a computer program could manage. One would get, for each number of rolls, the probability that all sums have appeared (an absorbing state). The expected number of rolls needed to reach the absorbing state could then be calculated numerically. –  hardmath May 31 '11 at 13:29
5  

2 Answers 2

Let $p_i$ denote the probability of throwing $i$, so that $p_2 = p_{12} = 1/36$, $p_7 = 1/6$, etc. Let $T_S$ denote the expected waiting time until all numbers appear, assuming that the subset $S$ of $\{2, \dots, 12\}$ has already appeared. We want to calculate $T_\emptyset$.

If an event has probability $p$ of occurring, the expected number of throws until the event occurs is $1/p$. (See geometric distribution.) The probability of something outside $S$ being thrown is $p_{S^c} = \sum_{i\not\in S}p_i$, so the expected number of throws until this happens is $1/p_{S^c}$. When this does happen, the number thrown is $i$ with probability $p_i/p_{S^c}$ (for $i \not\in S$). Then we start with set $S\cup \{i\}$ and wait. Thus,

$$ T_S = \frac{1}{p_{S^c}} + \sum_{i\not\in S} \frac{p_i}{p_{S^c}} T_{S\cup\{i\}}.$$

We can use this recurrence to calculate $T_\emptyset$. Doing this by hand is (as far as I can see) difficult because there are $2^{11}$ subsets, but it can be done exactly with a computer program. The answer turns out to be 769767316159/12574325400, which is about 61.2. Just to be sure we haven't made a mistake, we can check with a simulation whether this is about right, and it is. (All code used is in the first revision of this answer if anyone's interested.)

share|improve this answer

This is a kind of coupon collector problem, with unequal probabilities. It has been studied, but the formula for the expected waiting time seems quite (too?) complicated.

Here's the main paper (restricted - you can try to download it here: ftp://210.112.137.112/pub/Papers/schelling.pdf )

See also here.

share|improve this answer
    
Note that the formula involves a sum over (essentially) all subsets, so unless you have a lot of patience you'll need a computer anyway. :-) –  ShreevatsaR May 31 '11 at 14:56
    
Yes, I wonder if Max's answer, though wrong, is a good approximation. –  leonbloy May 31 '11 at 15:02

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.