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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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|cite|improve this question

marked as duplicate by joriki probability Jun 25 at 14:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

This sounds interesting. With one die its easy, see e.g. here: 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

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|cite|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: )

See also here.

share|cite|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

Not the answer you're looking for? Browse other questions tagged or ask your own question.