Roll me a prime

Probability Level 5

Optimus Prime loves prime numbers . So, he decides to keep rolling a fair six-sided die, until he rolls a prime number less than 100. e.g. If his last two rolls were a 6 and then a 1, he would be done since 61 is a prime number. Or, for example, any time he rolls a 3 he would also be done since 3 is a prime number.

If the expected number of rolls he must make is $\dfrac{a}{b}$ , where $a$ and $b$ are coprime positive integers , what is $a+b$ ?

Image credit: www.edplace.com

The answer is 11.

1 solution

Geoff Pilling
Jul 23, 2016

Let $E_n =$ The expected number of remaining rolls given that $n$ was the last number rolled.

Since 2, 3, and 5 are all prime, clearly $E_2 = E_3 = E_5 = 0$ .

Also, the only two digit primes starting with 1, 4 or 6 and ending with 1, 4, or 6 are 11, 41, and 61. Translating this to a set of linear equations, you get:

$E_0 = 1 + (1/6)*E_1 + (1/6)*E_4 + (1/6)*E_6$
$E_1 = 1 + (1/6)*E_4 + (1/6)*E_6$
$E_4 = 1 + (1/6)*E_4 + (1/6)*E_6$
$E_6 = 1 + (1/6)*E_4 + (1/6)*E_6$

The above equations are derived by considering states $0$ , $1$ , $4$ , and $6$ labeled by what the last number you rolled is (except for $0$ which is the state you start in). So, $E_n =$ The expected number of rolls from state $n$ . Then you can derive the above equations, for example for $E_1$ , from state $1$ you use up $1$ roll (the first term, $1$ ) and you have $1/6$ probability of getting to $4$ or $6$ . This translates to the second equation in the solution. You set up similar equations for $0$ , $4$ and $6$ .

Solving for $E_0$ , you get, $E_0 = 7/4$

$7+4 = \boxed{11}$

I get the first 2 equations. Can't seem to get my head around the last 2. Any extra explanation?

Peter van der Linden - 4 years, 10 months ago

Simpler: if there has been at least one roll and we're still going, rolling a 1 is also a success, because the previous roll must be one of 1, 4, 6 and all of 11, 41, 61 are primes. Thus given that there is a previous roll, the expected number of rolls $E'$ satisfies $E' = 1 + \frac{1}{3} E'$ , or $E' = \frac{3}{2}$ . At the beginning, there is no previous roll; either we roll 2, 3, or 5 and we win, or otherwise we need an expected number of $1 + E'$ rolls (1 for the first roll, $E'$ for the rest).

Ivan Koswara - 4 years, 10 months ago

Ah yes, very nice! ;)