Past exam of the mathematics course of the University of Cambridge / 2009 / ib / Paper 4 / 9H / Solution

Use coordinates $(i,j)\in \{0,\dots ,7{\}}^2$, with the starting corner $(0,0)$. The bishop stays on the 32 squares where $i+j$ is an even number. Its moves form a random walk on a graph, with an edge between distinct squares whenever $|i-i^{\prime }|=|j-j^{\prime }|$. If $d(i,j)$ is the number of reachable squares, the transition probability to each neighbor is $1/d(i,j)$.

The graph is connected: from $(i,j)$ move along its antidiagonal to $((i+j)/2,(i+j)/2)$, then along the main diagonal to the corner. The midpoint coordinates are integers because $i+j$ is an even number, and this square always lies on the board. Thus this is the full communicating state space of the bishop random walk.

The invariant distribution is proportional to degree. Its normalizing constant can be counted by summing the ordered pairs along each diagonal. The diagonals of one orientation have lengths $8,6,6,4,4,2,2$, contributing $144$; the other have lengths $1,3,5,7,7,5,3,1$, contributing $136$. ThereforeFor any neighboring states $s,t$, $\pi (s)P(s,t)=1/280=\pi (t)P(t,s)$, proving the detailed balance equations and hence that the chain is a reversible Markov chain.

The corner has seven neighbors. Kac's lemma gives its expected first positive return time: