## Knights tour revisited

Once again I have found food for thought in a post on John D Cook’s blog.

The puzzle posed:

*Start a knight at a corner square of an otherwise-empty chessboard. Move the knight at random by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?*

As is discussed this can be solved by considering a random walk on the Knight’s tour graph (connected graph).

I found it instructive to count the edges of the Knight’s tour graph (though I am disappointed that it was not as ‘clear’ to me as suggested). Consider the chessboard. The sum of the degrees of all the vertices is twice the number of edges.

Consider the following 6 6 board. The color represent distinguishes the degree of the vertices.

Using insights from this chessboard, see the table to derive the general formula:

Therefore, the number of edges for an Knight’s tour graph is: . This can be easily generalized to an chessboard to yield: . Thus, for the board the number of edges: 168.

Now, to address the puzzle. The Knight’s tour is a connected graph and the random walk on this graph is reversible. A unique solution vector, , can be found to , where is the transition matrix.

where is the degree of vertex

Note the denominator of is the sum of the degrees of the graph (or twice the number of edges).

Let be the graph of the mean transition time with the convention . Consider distinct states and . Considering the first step then recursively:

For mean recurrence time (),

Let be an matrix of all 1’s, by diagonal matrix with on the diagonals.

Integrating all these considerations, this can be represented as:

As we are dealing with a reversible Markov chain, ,

Hence,

Now ,

is a row vector such that , so

Therefore,

where is the cardinality of the edge set (the number of edges)…as explained by John D Cook.

I found the above approach here. It was easier for me to understand.

A 1000 run simulation yielded a mean of 163 (cf predicted 168):

An example walk is displayed below:

Reblogged this on Unkown Blogger Pursues a Deranged Quest for Normalcy.