2008 iTest Problems/Problem 26

Problem

Done working on his sand castle design, Joshua sits down and starts rolling a -sided die he found when cleaning the storage shed. He rolls and rolls and rolls, and after rolls he finally rolls a . Just rolls later he rolls the first 2 that first roll of . rolls later, Joshua rolls the first the first that he rolled the first that he rolled. His first rolls make the sequence . Joshua wonders how many times he should expect to roll the -sided die so that he can remove all but of the numbers from the entire sequence of rolls and (without changing the order of the sequence), be left with the sequence . 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 assume he starts by rolling the specific sequence of rolls above.)

Solution

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 . The probability of rolling n on roll 2 (but not roll 1) is . The probability of rolling n on roll 3 (but not rolls 1 or 2) is . In general, rolling your first n on roll k is . The expected total number of rolls needed to get your first n is .

The formula for a geometric series is . Taking derivatives of both sides gives So the expected number of rolls required to get face n is .

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 .