Question

On a chessboard compute the expected number of plays it takes a knight, starting in one of the four corners of the chessboard, to return to its initial position if we assume that at each play it is equally likely to choose any of its legal moves. (No other pieces are on the board.) Hint: Make use of Example 4.36.

Short answer

The expected number of plays for a knight to return to its initial position when starting in one of the four corners of the chessboard is approximately 168.4 plays. This is achieved by treating the knight's movement as a random walk, representing the chessboard with an 8x8 matrix, and using probability generating functions to compute the expected moves, taking into account all possible legal moves for the knight.

Step-by-step solution

Chessboard representation

We will represent the chessboard as an 8x8 matrix with each cell containing a probability generating function of a knight on that particular cell making all possible moves. In other words, we will treat the knight's movement as a random walk on the chessboard and use the probability generating function to compute the expected moves.

Movement options and generating functions

A knight can move in 8 different ways (2 cells in one direction and 1 cell in the perpendicular direction, or vice versa). Depending on the position, it can have up to 8 legal moves. So, for each cell, we will set the generating function as: \[ \frac{1}{n} (z_1 + z_2 + ... + z_n) \] where \(n\) represents the number of legal moves for the knight from that cell, and \(z_i\) denotes the next cell probability generating function.

Corner cell

From the corner of the chessboard (1,1), the knight has two legal moves: (3,2) and (2,3). Let G(1,1) be the generating function for the knight to return to the starting position (1,1). We now have a system of linear equations with the following variables G(1,1), G(3,2), and G(2,3). \[ G(1,1) = \frac{1}{2} (G(3,2) + G(2,3)) \]

Calculate for other cells

Using symmetry, we can generate equations for G(3,2) and G(2,3). Also, by considering the adjacency matrix, we can calculate the generating functions for G(3,2) and G(2,3) as: \[ G(3,2) = \frac{1}{6} (G(1,1) + G(5,1) + G(2,3) + G(3,4) + G(4,1) + G(5,3)) \] \[ G(2,3) = \frac{1}{6} (G(1,1) + G(3,1) + G(3,5) + G(4,3) + G(1,4) + G(4,1)) \]

Solving the equations

We now have a system of linear equations with the following variables: G(1,1), G(3,2), G(2,3), G(5,1), G(4,1), G(3,4), G(4,3), G(1,4), G(5,3) and G(3,5). Solving this system of linear equations yields the generating functions.

Compute expected number of plays

To find the expected number of plays the knight must take to return to the starting position, we must calculate the expected value of the generating function G(1,1). The expected value is simply the first derivative of G(1,1) evaluated at z = 1 (using random walk theory). Solving for the derivative and evaluating G'(1,1) at z = 1 gives us the expected number of plays. For this chessboard problem, the expected number of plays for a knight starting in one of the four corners to return to its initial position is around 168.4 plays.