Expected number of turns for a rook to move to top right-most corner?

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.$$


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.