Torus Chessboard

Let $E$ be the expected number of steps needed to get to the center from a corner square, and let $S$ be the expected number of steps needed to get to the center from a "side" square (a square that is neither a corner nor the center).

First, we note that expected values are additive. Next, we see that because of symmetry, the value of $E$ does not change depending on which corner we start from. Similarly, the value of $S$ does not change depending on what side square we start from.

We start from the corner. By moving down or to the right, we move the token to a side square. From that side square, the expected number of steps needed to get to the center square is $S$ .

By moving up or to the left, we move the token to a corner square. From that square, the the expected number of steps needed to get to the center square is $E$ . Since each movement counts as one step, we arrive at the equation

$E=\frac{1}{2}(S+1)+\frac{1}{2}(E+1)$ .

Now, let us say that we arrived at the side square. Because each step is independent of previous moves, we can find a similar equation for $S$ .

By moving in the direction of the center, we arrive at the center.

By moving in the opposite direction of the center, we arrive at another side square.

By moving in the other directions, we arrive at a corner square.

Because each count as one step, we also get the equation

$S=\frac{1}{4}(1)+\frac{1}{4}(S+1)+\frac{1}{2}(E+1)$ .

Solving these two equations, we get that $E=10$ .

Label corners as "a" and middle-squares (those along edges that aren't corners and aren't the center) as "b". Let A be the expected number of moves to end up on the center an "a", and B be the expected number of moves to end up on the center starting at a "b". By linearity of expectation, we have $A = 1 + \frac{A}{2} + \frac{B}{2}$ and $B = 1+ \frac{A}{2} + \frac{B}{4} +\frac{1}{4}\cdot 0$ . This is a simple linear system with $A=10,B=8$ , so our desired answer is 10.

Let a be the expected number of moves it would take for the token to end up on the center square starting from a corner square (all 4 are the same by symmetry), and let b the expected number of moves it would take for the token to end up on the center square starting from a side square (once again, symmetry).

Then a = 1+1/2 a+1/2 b and b = 1+1/2 a+1/4 b and we have a system of 2 equations. Solving, we get a = 10 and b = 8 so the answer is 10 moves.

We notice that the chessboard is made by $4$ corners, $4$ edges and $1$ center.

We call $c_n$ the number of ways to get to the center after $n$ moves (without touching the center before), $e_n$ the number of ways to get to any of the $4$ edges after $n$ moves and $a_n$ the number of ways to get to any of the $4$ corners after $n$ moves (all without touching the center before).

We now notice this recurrence:

$\begin{cases} c_n= e_{n-1}\\ e_n=e_{n-1}+2a_{n-1} \\ a_n=2(e_{n-1}+a_{n-1})\\ c_1=0\\ c_2=2 \end{cases}$

From the second and third equation we get:

$e_n=e_{n-1}+2a_{n-1}=e_{n-1}+4e_{n-2}+4a_{n-2}$

and having from the first equation that:

$4a_{n-2}=2e_{n-1}-2e_{n-2}$

we obtain:

$e_n=e_{n-1}+4e_{n-2}+2e_{n-1}-2e_{n-2}=3e_{n-1}+2e_{n-2}$

So we also get that:

$\begin{cases} c_n=3c_{n-1}+2c_{n-2}\\ c_1=0\\ c_2=2 \end{cases}$

From this recurrence relation we can get a formula for $c_n$ (and if you don't know how you can have a look here ):

$c_n=\frac{17-3\sqrt{17}}{34}\left( \frac{3+\sqrt{17}}{2}\right)^n+\frac{17+3\sqrt{17}}{34}\left( \frac{3-\sqrt{17}}{2}\right)^n$

Now we have that the probability of getting to the center for the first time after $n$ moves is:

$p_n=\frac{c_n}{4^n}$

and the expected number of moves is going to be:

$\displaystyle \sum_{i=1}^{\infty} i \cdot p_i=\sum_{i=1}^{\infty} i \cdot \frac{c_i}{4^i}$

that is the same as:

$\displaystyle \sum_{i=1}^{\infty}i\frac{17-3\sqrt{17}}{34}\left( \frac{3+\sqrt{17}}{8}\right)^i+i\frac{17+3\sqrt{17}}{34}\left( \frac{3-\sqrt{17}}{8}\right)^i$

This easily works out to be $\fbox{10}$ .

To see how have a look at Power Series

Define a middle square as a square which touches one of the sides of the board and is not a corner square.

Let the expected value of moves it will take the token on a corner square to end up on the center square of the board be $x$ and the expected value of moves it will take a token on a middle square to end up on the center square of the board be $y$ .

From a corner square, the token could move to 2 different corner squares and 2 different middle squares. After the first move, the expected value of the remaining number of moves is $\frac{2x+2y}{4} = \frac{x+y}{2}$ . Since $1$ move is already made, the total expected value of moves for a token on a corner square to go to the center square is $\frac{x+y}{2}+1 = \frac{x+y+2}{2}$ , which is equal to $x$ . Thus, we get $\frac{y+2}{2} = \frac{x}{2} \rightarrow y+2=x$ .

From a middle square, the token could move to 2 different corner squares, another middle square, or the center square. After that move, the expected value of the remaining moves is $\frac{2x+y+0}{4} = \frac{2x+y}{4}$ . Since 1 move was already made, the total number of expected moves is $\frac{2x+y}{4}+1 = \frac{2x+y+4}{4}$ , which is equal to y. Thus, we get $\frac{2x+4}{4} = \frac{3y}{4} \rightarrow \frac{x}{2}+1 = \frac{3y}{4}$ .

We have gotten the following $2$ equations: $y+2 = x$ and $\frac{x}{2}+1 = \frac{3y}{4}$ .

Substitute $x$ for $y+2$ to get $\frac{y+2}{2}+1 = \frac{3y}{4} \rightarrow \frac{y}{2}+2 = \frac{3y}{4} \rightarrow 2 = \frac{y}{4} \rightarrow y=8$ . Since $y=8$ , $x = 8+2=\boxed{10}$ .

When the token is not in the middle square, it is either in a corner space, or an edge space. Let $X$ represent the expected number of moves to get from a corner space to the middle and let $Y$ represent the expected number of moves to get from an edge space to the middle. If the token is in a corner space, there is a $\frac{1}{2}$ probability of it moving to an edge space and a $\frac{1}{2}$ probability of moving to another corner piece. From this we conclude that $X = 1 + \frac{1}{2}X + \frac{1}{2}Y$ . If the token is in an edge space, there is a $\frac{1}{4}$ probability of landing in the middle, $\frac{1}{4}$ probability of landing on a different edge space, and $\frac{1}{2}$ probability of landing on a corner space. From this we conclude that $Y =1 + \frac {1}{4} \cdot 0 + \frac{1}{4}Y + \frac{1}{2}X$ . Solving this system of two simultaneous equations give that $X = 10, Y = 8$ . Therefore $X = 10$ is the desired answer.