Unexpected Snakes and Ladders

Suppose $E_n$ is the expected number of moves required to reach square number $1+n$ from square number 1, our goal is to find $E_{99}$ .

Note that the starting square is arbitrary here, so this is exactly equivalent to saying that $E_n$ is the expected number of moves required to advance at least $n$ squares.

First and foremost, let's look at some trivial values:

• $E_0=0$ , we don't need to do anything to advance 0 squares, we are already at the target square!

• $E_{-1}=0$ , we already went past the target square (it is 1 square behind us), again we don't need to do anything (we define this as this will become useful later on).

• $E_1=1$ , no matter what number we roll, we will always advance at least 1 square, the expected number of moves to advance at least 1 square is 1.

---

Awesome, now that's out of the way, let's think about $E_n$ , in order to advance at least $n$ squares, you must either:

• Roll a $1$ , taking a move, and advance at least $n-1$ more squares

• Roll a $2$ , taking a move, and advance at least $n-2$ more squares

• Roll a $3$ , taking a move, and advance at least $n-3$ more squares

Since the probabilities of rolling each number are equal ( $=\frac{1}{3}$ ), we thus have, for $n\geqslant2$ , $E_n=\frac{1}{3}(1+E_{n-1})+\frac{1}{3}(1+E_{n-2})+\frac{1}{3}(1+E_{n-3})\text{ }$ $\therefore 3E_n=E_{n-1}+E_{n-2}+E_{n-3}+3\tag{1}$

Shift $n$ by 1: $3E_{n+1}=E_{n}+E_{n-1}+E_{n-2}+3\tag{2}$

$(2)-(1)\implies 3E_{n+1}-3E_n=E_n-E_{n-3}$

$\therefore 3E_{n+1}=4E_n-E_{n-3}$

This is a fourth order linear recurrence relation, its characteristic polynomial is $3r^4-4r^3+1=(r-1)^2(3r^2+2r+1)$ ( look up how to solve linear recurrence relations here ), equating this to 0 and solving this polynomial would yield roots $1$ (repeated) and $-\frac{1}{3}\pm\frac{\sqrt2}{3}i=\frac{1}{\sqrt3}e^{\pm i\theta}$ , where $\theta=\pi-\tan^{-1}\sqrt2$ , hence a solution to this recurrence relation is in the form $E_n=\left(\frac{1}{\sqrt3}\right)^n(c_1\cos n\theta+c_2\sin n\theta)+(c_3+c_4n)(1)^n$

Using $(1)$ to derive $E_2$ by plugging $n=2$ , we get $E_2=\frac{4}{3}$ .

Now with the initial conditions $E_{-1}=E_0=0$ , $E_1=1$ , $E_2=\frac{4}{3}$ , we can solve for $c_1$ , $c_2$ , $c_3$ and $c_4$ . After plugging in $n=-1, 0, 1, 2$ , we will get the following system of equations:

$\begin{cases} \sqrt3(c_1\cos\theta-c_2\sin\theta)+c_3-c_4=0 \\ c_1+c_3=0 \\ \frac{1}{\sqrt3}(c_1\cos\theta+c_2\sin\theta)+c_3+c_4=1 \\ \frac{1}{3}(c_1\cos2\theta+c_2\sin2\theta)+c_3+2c_4=\frac{4}{3}\end{cases}$

Where, $\cos\theta=\cos(\pi-\tan^{-1}\sqrt2)=-\frac{1}{\sqrt3},\text{ }\sin\theta=\sin(\pi-\tan^{-1}\sqrt2)=\sqrt{\frac{2}{3}},\text{ }\cos2\theta=2\cos^2\theta-1=-\frac{1}{3},\text{ } \sin2\theta=2\sin\theta\cos\theta=-\frac{2\sqrt2}{3}$ .

Solving the system of equations above, we have $c_1=-\frac13$ , $c_2=\frac1{6\sqrt2}$ , $c_3=\frac13$ , $c_4=\frac12$ .

$\therefore E_n=\left(\frac1{\sqrt3}\right)^n\left(-\frac13\cos n\theta+\frac1{6\sqrt2}\sin n\theta\right)+\frac13+\frac12n$

Finally, to find $E_{99}$ , all we need to do now is to set $n=99$ and it would give $E_{99}\approx49.833$ .