9
$\begingroup$

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?

  • 6
    http://math.stackexchange.com/questions/25568/a-question-about-dice/25576#255762011-05-31

2 Answers 2

9

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

4

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.

  • 0
    Yes, I wonder if Max's answer, though wrong, is a good approximation.2011-05-31