A knight stands in a corner of the chessboard. Assuming it makes each permissible move with equal probability, what's the expected number of moves for it to return to its starting point?

Do you know anything about Markov chains? There is a very simple method using invariant measure.

Kerwin

I know a little about Markov Chains, but I don't know about invariant measure. Could you elaborate?

A sufficient condition for a distribution to be invariant is that is satisfies the detail balance equation

Xj Pj,i=Xi Pi,j

(so called because we are balancing the transition i® j and j® i and we usually denote an invariant distribution by p. There is a theorem which states that under the assumption P is irreducible (i.e. any two states are in some way connected) and recurrent, there is essentially a unique positive invariant measure.

Moreover, in this case the following are equivalent:

(a) every state is positive recurrent;
(b) some state i is positive recurrent;
(c) P has an invariant distribution p.

(positive recurrent means the expected return time is finite)

In this example, we can treat the position of the knight as a Markov chain of random walk on some graph G. It is easy to see that an invariant measure associated to each vertex is the valency of the vertex. Now normalise the invariant measure to get the invariant distribution and apply the theorem. You should get 168.

Kerwin

Thanks, Kerwin. The theory of Markov chains is truly amazing.