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
-
1This sounds interesting. With one die its easy, see e.g. here: http://www.madandmoonly.com/doctormatt/mathematics/dice1.pdf p.9 – 2011-05-31
-
0What 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. – 2011-05-31
-
0@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? – 2011-05-31
-
0One 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. – 2011-05-31
-
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.
-
0Note that the formula involves a sum over (essentially) all subsets, so unless you have a lot of patience you'll need a computer anyway. :-) – 2011-05-31
-
0Yes, I wonder if Max's answer, though wrong, is a good approximation. – 2011-05-31