2008 iTest Problems/Problem 26

Problem

Done working on his sand castle design, Joshua sits down and starts rolling a $12$-sided die he found when cleaning the storage shed. He rolls and rolls and rolls, and after $17$ rolls he finally rolls a $1$. Just $3$ rolls later he rolls the first 2 $\textit{ after}$ that first roll of $1$. $11$ rolls later, Joshua rolls the first $3\textit{ after}$ the first $2$ that he rolled $\textit{after}$ the first $1$ that he rolled. His first $31$ rolls make the sequence $4,3,11,3,11,8,5,2,12,9,5,7,11,3,6,10,\textbf{1},8,3,\textbf{2},10,4,2,8,1,9,7,12,11,4,\textbf{3}$. Joshua wonders how many times he should expect to roll the $12$-sided die so that he can remove all but $12$ of the numbers from the entire sequence of rolls and (without changing the order of the sequence), be left with the sequence $1,2,3,4,5,6,7,8,9,10,11,12$. What is the expected value of the number of times Joshua must roll the die before he has such a sequence? (Assume Joshua starts from the beginning - do $\textit{not}$ assume he starts by rolling the specific sequence of $31$ rolls above.)


Solution

$\boxed{144}$

The expected number of rolls required to get any particular face of the die is 12 rolls. The proof goes as follows: the probability of rolling n on roll 1 is $(\frac{1}{12})$. The probability of rolling n on roll 2 (but not roll 1) is $(\frac{11}{12})\cdot (\frac{1}{12})$. The probability of rolling n on roll 3 (but not rolls 1 or 2) is $(\frac{11}{12})^2 \cdot (\frac{1}{12})$. In general, rolling your first n on roll k is $(\frac{11}{12})^{(k-1)} \cdot (\frac{1}{12})$. The expected total number of rolls needed to get your first n is $1\cdot \frac{1}{12}+2\cdot (\frac{11}{12})(\frac{1}{12})+3\cdot (\frac{11}{12})^{2}(\frac{1}{12})+4\cdot (\frac{11}{12})^3(\frac{1}{12})+\cdots = \sum_{k=1}^{\infty}{k\cdot (\frac{11}{12})^{(k-1)}(\frac{1}{12})}$.

The formula for a geometric series is $\sum_{n=0}^{\infty}{x^n}=\frac{1}{1-x}$. Taking derivatives of both sides gives $\sum_{n=1}^{\infty}{n\cdot x^{n-1}}=\frac{1}{(1-x)^2}$ So the expected number of rolls required to get face n is $\frac{\frac{1}{12}}{(1-\frac{11}{12})^2}=12$.

Rolling a sequence to get a first n can be thought of as an independent trial and getting the full sequence of {1,2,3,4,5,6,7,8,9,10,11,12} can be thought of as running 12 independent trials: trial 1 to get your first 1, then trial 2 to roll your first 2 (after the first 1), then trial 3 to roll the first 3 (after the first 2 after the first 1) etc... All of these 12 trials can be concatenated together to get the final required sequence.

Thus the total expected roll count is $12\cdot 12 = 144$.

See Also

2008 iTest (Problems)
Preceded by:
Problem 25
Followed by:
Problem 27
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100