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?
Throwing All Numbers From 2 to 12 With Two Dice
-
6http://math.stackexchange.com/questions/25568/a-question-about-dice/25576#25576 – 2011-05-31
2 Answers
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.)
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.
-
0Yes, I wonder if Max's answer, though wrong, is a good approximation. – 2011-05-31