A chess piece is wandering around on an otherwise vacant 8 8 chessboard. At each move

Chapter 11, Problem 12

(choose chapter or problem)

A chess piece is wandering around on an otherwise vacant \(8 \times 8\) chessboard. At each move, the piece (a king, queen, rook, bishop, or knight) chooses uniformly at random where to go, among the legal choices (according to the rules of chess, which you should look up if you are unfamiliar with them).

(a) For each of these cases, determine whether the Markov chain is irreducible, and whether it is aperiodic.

Hint for the knight: Note that a knight's move always goes from a light square to a dark square or vice versa. A knight's tour is a sequence of knight moves on a chessboard such that the knight visits each square exactly once. Many knight's tours exist.

(b) Suppose for this part that the piece is a rook, with initial position chosen uniformly at random. Find the distribution of where the rook is after n moves.

(c) Now suppose that the piece is a king, with initial position chosen deterministically to be the upper left corner square. Determine the expected number of moves it takes the king to return to that square, fully simplified, preferably in at most 140 characters.

(d) The stationary distribution for the random walk of the king from the previous part is not uniform over the 64 squares of the chessboard. A recipe for modifying the chain to obtain a uniform stationary distribution is as follows. Label the squares as 1, 2,..., 64, and let \(d_{i}\) be the number of legal moves from square i. Suppose the king is currently at square i. The next move of the chain is determined as follows:

Step 1: Generate a proposal square j by picking uniformly at random among the legal moves from i.

Step 2: Flip a coin with probability \(\min\left(d_i/d_j,\ 1\right)\) of Heads. If the coin lands Heads, go to j. Otherwise, stay at i.

Show that this modified chain has a stationary distribution that is uniform over the 64 squares.