[Math] Probability a knight on a chess board is back where it started after $n$ moves

markov chainsprobabilityprobability distributionsprobability theoryprobability-limit-theorems

I'm trying to work my way through a problem concerning a random walk by a knight on a chessboard.

I've modeled the board as a graph with 64 vertices and the random walk on the graph as a Markov chain to find the stationary distribution and I've used this to show that if the knight starts in the bottom left corner then the mean return time is 168 moves.

Now, I'm asked to let $p_n$ be the probability that the knight is back in the same corner after $n$ steps, and describe the behaviour of $p_n$ as $n \rightarrow \infty$.

I'm pretty sure the knight's walk has period 2 so I can't apply the theorem for convergence to equilibrium directly. For odd $n$, clearly $p_n = 0$.

How would I go about finding the limit if $n$ is even? Intuitively it seems like it would be $\frac{1}{84}$ ($= \frac{2}{168}$), but I don't know how to go about providing a proof of that.

I'd really appreciate some help.

Best Answer

Consider a graph whose nodes are the black squares of the chessboard. At each black square, find the probability with which a consecutive pair of knight moves would land on each other black square. This gives a transition matrix for a Markov process that consists of pairs of knight moves.

In fact this new Markov process is just a way of describing all the even-numbered states of the original process (if you consider the starting state to be state number zero). If your mean return time to the bottom left corner is $168$ in the original process, it is $84$ in the new process.