Welcome to NRICH.

 
Chess expectation
By Edwin Koh on Saturday, November 30, 2002 - 02:22 am:

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?

By Kerwin Hui on Saturday, November 30, 2002 - 09:27 am:

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

Kerwin

By Edwin Koh on Saturday, November 30, 2002 - 11:18 am:

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

By Kerwin Hui on Saturday, November 30, 2002 - 01:12 pm:

A distribution X is invariant if XP=X (P is the transition matrix) and Xi³0. (If Xi are merely nonnegative, we say X is an invariant measure.)

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

XjPj,i=XiPi,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.
In the case when (c) holds, the expected return time of state i starting at i is 1/pi.
(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
By Edwin Koh on Monday, December 02, 2002 - 02:03 am:

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