13

Suppose a rook starts on the lower left-most square of a standard $8 \times 8$ chess board. The board contains no other pieces.

The rook randomly makes a legal chess move with every turn (directly vertical or horizontal). The rook cannot remain stationary during a turn. What is the expected number of moves for the rook to land on the upper right-most square?

I understand the rook has 14 possible moves for every turn. The problem seems to fit the concept of Markov chains, as the probability distribution of any given move does not depend on the previous. However, I do not understand how to approach this calculation.

nande2121
  • 203

3 Answers3

27

Label the board as $\{1,2,\cdots,8\}\times\{1,2,\cdots,8\}$. A key remark is that the number of coordinates of the position of the rook which are equal to $8$ performs a Markov chain, and, obviously, the upper rightmost square is the only square on the board such that this number is $2$. Thus, one asks for the mean hitting time of $2$ by a Markov chain on $\{0,1,2\}$ starting from $0$ with transition probabilities as follows:

  • Transition $0\to0$: probability $\frac67$
  • Transition $0\to1$: probability $\frac17$
  • Transition $1\to0$: probability $\frac12$
  • Transition $1\to1$: probability $\frac37$
  • Transition $1\to2$: probability $\frac1{14}$

Then the usual approach works: one considers the mean hitting time $t_k$ starting from state $k$, then $t_2=0$ and, conditioning on the first step of the Markov chain, one gets $$t_0=1+\tfrac67\cdot t_0+\tfrac17\cdot t_1,\qquad t_1=1+\tfrac12\cdot t_0+\tfrac37\cdot t_1+\tfrac1{14}\cdot0,$$ hence the desired expected time is $$t_0=70.$$ Perhaps surprisingly, starting from the square G7 it takes exactly as many steps to reach the (apparent) neighbour square H8 than starting from the (apparent) farthest square A1.

More generally, for a board of size $n\times n$, $$t_0=n^2+n-2.$$

Did
  • 279,727
  • @paw88789 Which answer was that? – Did Oct 29 '14 at 10:23
  • The fact that the move is to move to a random square in the same column or row - i. e. change one coordinate uniformly at random - explains why G7 is no closer to H8 than A1 is. – Michael Lugo Oct 29 '14 at 17:47
10

You can simplify this problem quite a bit by noting that we can classify squares on the board as being in one of three sets: Set $A$ is the set of $49$ squares that are not in the row or column of the target square; set $B$ is the set of $14$ squares that are in the row or column of the target square, but not the target square itself; and set $C$ is the set of the target square.

If the rook is (on a square) in $A$, it has transition probabilities of $P(A\to A)=\frac{12}{14}=\frac{6}{7}$, and $P(A\to B)=\frac{2}{14}=\frac17$. If the rook is in set $B$, the transition probabilities are $P(B\to A)=\frac12$, $P(B\to B)=\frac37$, and $P(B\to C)=\frac1{14}$.

If we let $E_A$ be the expected number of moves to get from $A$ to $C$ and $E_B$ be the expected number of moves from $B$ to $C$, we can set up the following equations:

$E_B=\frac{1}{14}\cdot 1+\frac{3}{7}(E_B+1)+\frac{1}{2}(E_A+1)$ and

$E_A=\frac17(E_B+1)+\frac67(E_A+1)$.

You should be able to solve this system for $E_A$ and $E_B$ to finish off the problem.

paw88789
  • 40,402
  • For the impatient, you can see the results at http://www.wolframalpha.com/input/?i=x%3D1%2F14%2B3%2F7%28x%2B1%29%2B1%2F2%28y%2B1%29%2C+y%3D1%2F7%28x%2B1%29%2B6%2F7%28y%2B1%29. – Dancrumb Oct 29 '14 at 15:11
1

Lets keep it simple. Wherever you are on the board, there are 14 possible moves. Therefore, every calculation will be considered in a fraction of 14. As we only need the likely amount of moves, we'll treat every chance as absolute.

If you are on one of the two edges that can reach the destination in one move, there is a 1/14 chance of reaching it. That means that it takes 14 moves on the edge to reach the destination.

There is a 7/14, or a 1/2, chance of moving away from the edge, back to where you need two moves to reach the destination. Since you need to be on the edge 14 times before reaching the destination, 14/2 is 7. You'll move away from the edge 7 times.

When away from the edge, it takes a 2/14, or a 1/7, chance of returning to a proper edge. That means 7 moves before reaching it. When combined with the previous short paragraph, we can multiply 7 by 7 to reach 49 moves. That is how many times it takes to reach 14 moves on the edge.

So, we get 49+14 = 63. But wait! We don't start on the edge, we start on the opposing square. So we need another 7 moves to reach a proper edge. 63+7 = 70.

It takes 70 moves to reach the destination, starting from the opposing corner.

Crosby
  • 11