In a dice race of degree \(m\) and length \(n\), each player chooses a sequence of \(m\) die rolls. Then we roll a die \(n\) times to generate the race sequence. The player whose sequence occurs first in the race sequence wins. If no player’s sequence occurs in the race sequence, the race is a tie. (If we want to guarantee a winner, we can always set \(n = \infty\).)
For example, say you and I run a race of degree \(m=2\) and length \(n=20\). I might choose 55 as my sequence. You might choose 23. Then we roll a die \(n=20\) times to generate the race sequence:
6 1 6 6 1 5 5 3 1 4 5 2 3 3 2 2 6 4 3 4
In this race, I would win since 55 occurred before 23 in the race sequence.
Now consider the following questions:
- Given a choice between 55 and 23, which should you choose? Why?
- In an infinite-length race of degree \(m=2\), what is the expected number of die rolls before 55 occurs? What about for 23?
- Write code to run a dice race, given degree \(m\), length \(n\), and the players’ chosen sequences.
- Use the code to simulate many races between 55 and 23.
- How do the results compare with your answer to question 2?
I’ll answer the first two questions in this post and save the rest for a later post.
(Now would be a good time to pause and try to answer the questions yourself.)
Question 1: Given a choice between 55 and 23, which should you choose? Why?
In the example above, 55 won the race. Is it the better choice, in general? To answer the question, let’s think about the task of matching the sequence 55 in a series of die rolls. This task can be modeled as a finite automaton:
We start in the initial state S0. If the next die roll is a 5, we advance to state S1; otherwise, we remain at S0. If we’re at S1 and the next roll is another 5, we advance to S2 and have successfully matched the sequence 55; otherwise, we go all the way back to S0 and start over from the beginning.
Now let’s consider the automaton for the sequence 23:
It’s similar to the automaton for 55 except that when in state S1, we have a 1-in-6 chance to stay at S1. Failure to advance does not always force us to start over at S0. That reduced risk gives the sequence 23 an advantage over 55.
So, given a choice between 55 and 23, you should choose to race with 23.
Question 2: In an infinite-length race of degree \(m=2\), what is the expected number of die rolls before 55 occurs? What about for 23?
To answer this question, we’ll have to use a little algebra and probability theory. Let’s start by finding the expected number of rolls needed to win with the sequence 55.
Let \(x_i\) be the expected number of die rolls needed to reach state S2 from S\(i\). We want to find \(x_0\), the expected number of rolls needed to reach the “match” state S2 from the initial state S0. Referring to the diagram for the 55 automaton, we know that \(x_0\) must satisfy the equation
\[ x_0 = 1 + \tfrac{5}{6} x_0 + \tfrac{1}{6} x_1. \]
That’s because from S0 we must roll one die for a chance to advance, and, once rolled, we have a 5/6 probability of remaining at S0 and a 1/6 probability of advancing to S1. If we remain at S0, the expected cost to reach S2 is \(x_0\); and if we advance to S1, the expected cost to reach S2 is \(x_1\). (While this reasoning is intuitive, it is also justified by the law of total expectation.)
Using similar logic, we can find the equation for \(x_1\):
\[ x_1 = 1 + \tfrac{5}{6} x_0 + \tfrac{1}{6} x_2. \]
And the equation for \(x_2\) is trivial, since it takes zero rolls to reach S2 from S2:
\[ x_2 = 0. \]
Now it’s a matter of solving the system of equations for \(x_0\), \(x_1\), and \(x_2\). Substituting 0 for \(x_2\) in the equation for \(x_1\) gives
\[ x_1 = 1 + \tfrac{5}{6} x_0. \]
And substituting this expression for \(x_1\) in the equation for \(x_0\) gives
\[ x_0 = 1 + \tfrac{5}{6} x_0 + \tfrac{1}{6} \left( 1 + \tfrac{5}{6} x_0 \right) = \tfrac{7}{6} + \tfrac{35}{36} x_0. \]
Subtracting \(\tfrac{35}{36} x_0\) from both sides gives us
\[ \tfrac{1}{36} x_0 = \tfrac{7}{6}. \]
And multiplying both sides by 36 solves the equation:
\[ x_0 = \tfrac{7}{6}(36) = (7)(6) = 42. \]
So, on average, you need 42 rolls to find your sequence when you choose 55.
Now let’s consider the case when you choose 23 as your sequence. Referring to the diagram for the 23 automaton, the corresponding equations are:
\[\begin{align} x_0 & = 1 + \tfrac{5}{6} x_0 + \tfrac{1}{6} x_1 \\ x_1 & = 1 + \tfrac{4}{6} x_0 + \tfrac{1}{6} x_1 + \tfrac{1}{6} x_2 \\ x_2 & = 0 \end{align}\]
Solving this system of equations (I’ll skip the algebra), we find that \(x_0 = 36\).
So, on average, you need 36 die rolls to find your sequence when you choose 23. That’s notably faster than 42 rolls when you choose 55.