2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Math.SE. I've worked on numerical simulations on this knight chess board problem to find out the mean return time of the knight. Maybe Norris's Markov chain chapter one can help. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Sep 28 '18 at 15:05
  • $\begingroup$ By saying knights path has period 2, what is meant? That it alternates black, white squares? $\endgroup$ – coffeemath Sep 28 '18 at 15:06
  • $\begingroup$ Without remembering much Markov chain theory, my immediate guess would be $\frac{2}{168}$ at high even $n$, rather than $\frac{1}{64}$. $\endgroup$ – Henning Makholm Sep 28 '18 at 15:08
  • 1
    $\begingroup$ Your intuition of 1/64 implies that it's equally likely for a knight to wind up on any square, but I'm not sure that's correct. For a square near the center of the board, the knight has 8 possible positions that it could have come from. For a square at the edge, the knight has 4 ways of getting there. For a corner square, there's only 2 possible squares the knight could have come from. I'd expect it to be more likely for the knight to finish near the center than an edge or a corner. $\endgroup$ – Nuclear Wang Sep 28 '18 at 15:09
  • $\begingroup$ Sorry, my 1/64 was a typo - I meant to put 1/84. My thinking is that if 168 is the mean return time then the probability of it being there only on an even move would be double 1/168. As I say, that was my first guess but I could be wrong. $\endgroup$ – oxonian1 Sep 28 '18 at 15:13
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.