Knight returning to corner on chessboard -- average number of steps

Question

Context: My friend gave me a problem at breakfast some time ago. It is supposed to have an easy, trick-involving solution. I can't figure it out.

Problem: Let there be a knight (horse) at a particular corner (0,0) on a 8x8 chessboard. The knight moves according to the usual rules (2 in one direction, 1 in the orthogonal one) and only legal moves are allowed (no wall tunnelling etc). The knight moves randomly (i.e. at a particular position, it generates a set of all possible and legal new positions, and picks one at random). What is the average number of steps after which the knight returns to its starting corner?

To sum up: A knight starts at (0,0). How many steps on average does it take to return back to (0,0) via a random (but only legal knight moves) walk.

My attempt: (disclaimer: I don't know much about Markov chains.)

The problem is a Markov chain. There are $8\times8 = 64$ possible states. There exist transition probabilities between the states that are easy to generate. I generated a $64 \times 64$ transition matrix $M_{ij}$ using a simple piece of code, as it seemed too big to do by hand.

The starting position is $v_i = (1,0,0,...) = \delta_{0i}$.

The probability that the knight as in the corner (state 0) after $n$ steps is $$ P_{there}(n) = (M^n)_{0j} v_j \, . $$ I also need to find the probability that the knight did not reach the state 0 in any of the previous $n-1$ steps. The probability that the knight is not in the corner after $m$ steps is $1-P_{there}(m)$.

Therefore the total probability that the knight is in the corner for the first time (disregarding the start) after $n$ steps is $$ P(n) = \left ( \prod_{m=1}^{n-1} \left [ 1 - \sum_{j = 0}^{63} (M^m)_{0j} v_j \right ] \right ) \left ( \sum_{j = 0}^{63} (M^n)_{0j} v_j \right ) $$ To calculate the average number of steps to return, I evaluate $$ \left < n \right >= \sum_{n = 1}^{\infty} n P(n) \, . $$ My issue: The approach I described should work. However, I had to use a computer due to the size of the matrices. Also, the $\left < n \right >$ seems to converge quite slowly. I got $\left < n \right > \approx 130.3$ numerically and my friend claims it's wrong. Furthermore, my solution is far from simple. Would you please have a look at it?

Thanks a lot! -SSF

Answer 1

Details of the method mentioned in @Batman's comment:

We can view each square on the chessboard as a vertex on a graph consisting of $64$ vertices, and two vertices are connected by an edge if and only if a knight can move from one square to another by a single legal move.

Since knight can move to any other squares starting from a random square, then the graph is connected (i.e. every pair of vertices is connected by a path).

Now given a vertex $i$ of the graph, let $d_i$ denote the degree of the vertex, which is number of edges connected to the vertex. This is equivalent to number of possible moves that a knight can make at that vertex (square on chessboard). Since the knight moves randomly, transition probabilities from $i$ to its neighbors is $1/d_i$.

Now since the chain is irreducible (since the graph is connected) the stationary distribution of the chain is unique. Let's call this distribution $\pi$. Now we claim the following:

Claim Let $\pi_j$ denote $j^\text{th}$ component of $\pi$. Then $\pi_j$ is proportional to $d_j$.

Proof Let $I$ be the fuction on vertices of the graph such that $I(i)=1$ if $i$ is a neighbor of $j$, and $I(i)=0$ otherwise. Then

$$ d_j=\sum_i I(i)=\sum_i d_i \cdot \frac{I(i)}{d_i} = \sum_i d_i p_{ij} $$ where $p_{ij}$ is the transition probability from $i$ to $j$. Hence we have $dP=d$ where $P$ is the transition matrix of the chain, and $d=(d_1,\cdots,d_j,\cdots,d_{64})$. Thus $\pi P=\pi \implies$ Claim

Therefore, it follows that after normalising we have

$$ \pi_j=d_j/\sum_i d_i $$

Finally we recall the following theorem

Theorem If the chain is irreducible and positive recurrent, then

$$ m_i=1/\pi_i $$ Where $m_i$ is the mean return time of state $i$, and $\pi$ is the unique stationary distribution.

Thus if we call the corner vertex $1$, we have

$$ m_1=1/\pi_1 $$

You can check that $\sum_i d_i = 336$, and we have $d_1=2$ (at corner knight can make at most $2$ legal moves. Therefore $\pi_1=1/168$ and

$$ m_1=168 $$

Answer 2

The first thing we do is find a stable distribution for the Markov process. We see that the process will be stable if the mass for each square of the chessboard is proportional to the number of knight moves leading away from it; then the process will move a mass of 1 along each possible knight move, so each square with n moves from it will have a mass of n moving in and a mass of n moving out, so everything balances.

Next, we want to find the total mass of the system. This is the total number of possible knight moves; there are 8 possible directions a knight can move, and each direction can start from a 6x7 square, so there will be 8*6*7 = 336 possible moves, and that is the total mass of the distribution.

Since a corner square has a mass of 2, that represents 2/336 = 1/168 of the mass of the distribution. Since we have a connected recurrent process, an infinite random walk from any square will be at that particular corner 1/168 of the time. That means the average time between visits to the corner will be 168.