Expected length of generating a pattern (throwing dice)

Question

A fair die is tossed repeatedly. The experiment ends as soon as the last six outcomes form the pattern 131131

What is the expected length (i.e. the number of rolls of the die) of this experiment?

Answer 1

Conway's algorithm would compare identical terms on the left and right of 131131:

• length $1$: yes 1 both sides
• length $2$: no 13 on left, 31 on right
• length $3$: yes 131 both sides
• length $4$: no 1311 on left, 1131 on right
• length $5$: no 13113 on left, 31131 on right
• length $6$: yes 131131 both sides

So you have yes for $1$, $3$ and $6$, and $6$ faces on a die so the expected time is $6^1+6^3+6^6=46878$

Answer 2

I thought I would add my solution to this here as well, in case it may help others. There are other ways to do this. One is a way to do this using Markov Chains. This will work even in cases when the dice is not a fair dice.

Markov Chain Method

You can construct the chain as follows (I just used different colors to disambiguate):

Let state 0 be nothing i.e. similar to starting afresh.

Note that state 131131 is absorbent i.e. $P($state 131131 to state 131131$)\ = 1$.

Let $\psi(i)$ be the expected number of throws to reach state 131131 from state $i$

We now have equations as follows:

$\psi(13113) = 1 + \frac{5}{6}\psi(0)$

$\psi(1311) = 1 + \frac{1}{6}\psi(1) + \frac{4}{6}\psi(0) + \frac{1}{6}\psi(13113)$

$\psi(131) = 1 + \frac{1}{6}\psi(13) + \frac{4}{6}\psi(0) + \frac{1}{6}\psi(1311)$

$\psi(13) = 1 + \frac{5}{6}\psi(0) + \frac{1}{6}\psi(131)$

$\psi(1) = 1 + \frac{1}{6}\psi(1) + \frac{4}{6}\psi(0) + \frac{1}{6}\psi(13)$

$\psi(0) = 1 + \frac{5}{6}\psi(0) + \frac{1}{6}\psi(1)$

Solve the system of equations for $\psi(0)$ i.e. the expected number of throws to reach 131131 from state 0. You will get:

$\psi(0)=46878$

Extra

Additionally, if you want a bunch of intermediate results, you get:

$\psi(1)=46872$

$\psi(13)=46842$

$\psi(131)=46656$

$\psi(1311)=45576$

$\psi(13113)=39066$