Problem Statement

How many times do we have to roll a fair 6-sided die till we roll two numbers in a row that differ by 2?

Original Problem Link: Click here

Solution

Here, starting from the first roll, ofcourse each number is equally likely to show, with a probability of \(1/6\). Hypothetically, we could compute each possible suitable combination (1-3, 3-1, 2-4, 4-2 …) and compute its probability. Summing this in the standard method of computing Expectation, we could get the answer, but clearly this method is very tedious, time-consuming and computationally heavy.

A better alternative is to use the concept of Conditional Expectations. It essentially states that

\[E[X] = \sum_{Y_i} E[X \mid Y_i] P(Y_i)\]

Step 1: Identifying States

In the described problem, the dice can show 6 possible faces. This means, we can identify 6 different unique states \(S_{1}\), \(S_{2}\), \(S_{3}\), \(S_{4}\), \(S_{5}\), \(S_{6}\).

This reduces our problem to a Markov Chain analysis, with transition probablities from each state to each other state as \(1/6\).

How? Essentially, each State \(S_{i}\) represents that the die showed i in the first roll. If I roll it again, then either the number will differ by 2 (leading to the simulation being stopped there), or it will show another number, and our analysis essentially “resets” with a new number as our first number. (Ofcourse we will account for the fact that we did take 1 roll to each this new State).

We also note another interesting observation here.

I propose this - “The expected no. of rolls for our problem, given that the first roll returned 1, is the same as the expected no. of rolls given that the first roll returned 6”

How? Simply because 1 and 6 are essentially symmetric. If I get 1 as my first roll, only 3 in the next roll would stop my simulation (Thus only 1 possible value will stop). Same goes for 6 (only 4 can fulfill the condition). Infact, same goes for 2 and 5!. If I get 2, only 4 can stop, and if I get 5, only 3 can stop my simulation.

Thus, \(E[X \mid 1] = E[X \mid 2] = E[X \mid 5] = E[X \mid 6]\), where \(E[X \mid i]\) represents the expected number of turns, given that the die started from face i.

As you may have guessed, we can do a similar analysis for \(E[X \mid 3]\) and \(E[X \mid 4]\). If my first roll gives 3, I have 2 possible cases (1 and 5) where my simulation ends in the next step. Same for if my first roll gives 4, because then either 2 or 6 will stop the simulation. Thus, by symmetry, \(E[X \mid 3] = E[X \mid 4]\).

Now, yet another fact!

Clearly, \(E[X] = 1/6 (1 + E[X \mid 1]) + 1/6 (1 + E[X \mid 2]) + 1/6 (1 + E[X \mid 3]) + 1/6 (1 + E[X \mid 4]) + 1/6 (1 + E[X \mid 5]) + 1/6 (1 + E[X \mid 5])\)

How? - Exercise to reader!

Thus, we can reduce the problem to

“Given the state transition probability 1/6 and the dependence between the states, find \(E[X \mid 1]... E[X \mid 6]\), where \(X\) is the event of getting 2 rolls differing by 2, and \(E[X \mid i]\) represents starting the experiment with face i”

Step 2: Forming the set of Expectation equations

For each state \(i\), we compute \(E[X\mid i]\). But as discussed, since there is symmetry, it is sufficient to just compute \(E[X \mid 1]\) and \(E[X \mid 3]\).

Now,

\[E[X \mid 1] = \frac{1}{6} (E[X \mid 1,1]) + \frac{1}{6} (E[X \mid 1,2]) + \frac{1}{6} (E[X \mid 1,3]) + \frac{1}{6} (E[X \mid 1,4]) + \frac{1}{6} (E[X \mid 1,5]) + \frac{1}{6} (E[X \mid 1,6])\]

Substituting:

  • \(E[X \mid 1,3] = 1\) since rolling a 3 stops the process. (Thus only 1 step required till 3 from 1)
  • \(E[X \mid 1,j] = 1 + E[X \mid j]\) for all other \(j\), since the process resets but after one step.

Thus,

\[E[X \mid 1] = \frac{1}{6} (1 + E[X \mid 1]) + \frac{1}{6} (1 + E[X \mid 2]) + \frac{1}{6} (1) + \frac{1}{6} (1 + E[X \mid 4]) + \frac{1}{6} (1 + E[X \mid 5]) + \frac{1}{6} (1 + E[X \mid 6])\]

Similarly, for \(E[X \mid 3]\):

\[E[X \mid 3] = \frac{1}{6} (E[X \mid 3,1]) + \frac{1}{6} (E[X \mid 3,2]) + \frac{1}{6} (E[X \mid 3,3]) + \frac{1}{6} (E[X \mid 3,4]) + \frac{1}{6} (E[X \mid 3,5]) + \frac{1}{6} (E[X \mid 3,6])\]

Substituting:

  • \(E[X \mid 3,1] = 1\), since rolling a 1 stops the process.
  • \(E[X \mid 3,5] = 1\), since rolling a 5 stops the process.
  • \(E[X \mid 3,j] = 1 + E[X \mid j]\) for all other \(j\).

Thus,

\[E[X \mid 3] = \frac{1}{6} (1) + \frac{1}{6} (1 + E[X \mid 2]) + \frac{1}{6} (1 + E[X \mid 3]) + \frac{1}{6} (1 + E[X \mid 4]) + \frac{1}{6} (1) + \frac{1}{6} (1 + E[X \mid 6])\]

Step 3: Solving the equations

Now, using:

\[a = E[X \mid 1] = E[X \mid 2] = E[X \mid 5] = E[X \mid 6]\] \[b = E[X \mid 3] = E[X \mid 4]\]

Substitute these into the equations made above, and simplify, to get:

\[a = 1 + \frac{1}{6} (a + a + b + a + a)\] \[b = 1 + \frac{1}{6} (a + a + b + b)\]

Solving these, we get:

\[a = 5, \quad b = 4\]

Finally, computing \(E[X]\):

\[E[X] = 1 + \frac{1}{6} (a + a + b + b + a + a) = 1 + \frac{4a + 2b}{6}\] \[E[X] = 1 + \frac{4 \times 5 + 2 \times 4}{6} = 1 + \frac{14}{3}\] \[E[X] = \frac{17}{3}\]

Therefore, the expected number of moves required for the ant to reach back to its starting point is \(\frac{17}{3}\)

💡 Did you enjoy this problem? Check out more puzzles in the Problems section!