Another Knight On The Tiles

We do not have to consider a Markov chain on all $64$ squares of the chessboard. There are $10$ types of square on a chessboard (distinguished by the number and type of squares that a knight can reach from them), as shown in the diagram, and we see that the safe zone consists of all the squares of type $10$ . If we consider a Markov chain on the $10$ classes of squares, then the transition matrix for this chain is

$M \; = \; \left( \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac13 & 0 & 0 & 0 & \frac13 & \frac13 & 0 & 0 \\ 0 & \frac14 & 0 & 0 & 0 & \frac14 & \frac14 & 0 & \frac14 & 0 \\ 0 & 0 & 0 & 0 & \frac14 & \frac14 & 0 & \frac14 & \frac14 & 0 \\ 0 & 0 & 0 & \frac12 & 0 & 0 & 0 & 0 & \frac12 & 0 \\ \frac16 & 0 & \frac16 & \frac16 & 0 & 0 & \frac16 & 0 & \frac16 & \frac16 \\ 0 & \frac16 & \frac16 & 0 & 0 & \frac16 & 0 & \frac16 & \frac16 & \frac16 \\ 0 & \frac14 & 0 & \frac14 & 0 & 0 & \frac14 & 0 & 0 & \frac14 \\ 0 & 0 & \frac18 & \frac18 & \frac18 & \frac18 & \frac18 & 0 & \frac14 & \frac18 \\ 0 & 0 & 0 & 0 & 0 & \frac14 & \frac14 & \frac14 & \frac14 & 0 \end{array} \right)$

This is a finite irreducible (so non-null recurrent) Markov chain, which can be seen as identical to the random walk on the following multigraph (with a loop), so that the transition probability from state $i$ to state $j$ is equal to $p_{ij} \; = \; \left\{ \begin{array}{lll}\frac{n_{ij}}{s_i} & \hspace{1cm} & \mbox{if } j \mbox{ is connected to } i \mbox{ by at least one edge}, \\ 0 & & \mbox{otherwise} \end{array}\right.$ where $n_{ij}$ is the number of termini of edges at state $i$ that lead to state $j$ , and $s_i \; = \; \sum_j n_{ij}$ is the scope of the state $i$ . Note that, in the case of state $9$ , which possesses a loop, we have $n_{99} = 2$ and $s_9 = 8$ . For all other values of $i$ and $j$ , $n_{ij}$ is either $1$ or $0$ . We want to know the expected return time from state $10$ to state $10$ .

Since $s_i p_{ij} \; = \; s_j p_{ji}$ for each $i,j$ , since this expression is equal to $n_{ij}$ whenever there is an edge from $i$ to $j$ , and $0$ otherwise, we see that $\pi_i \; = \; \frac{s_i}{s} \hspace{2cm} 1 \le i \le 10$ is the (unique) invariant distribution for this Markov chain, where $s = \sum_{i=1}^{10}s_i$ . We note that $s_{10} = 4$ and $s = 42$ , so that (by standard Markov chain theory) the expected return time from state $10$ to state $10$ is $\pi_{10}^{-1} = \frac{21}{2}$ , making the answer $21 + 2 = \boxed{23}$ .

Alternatively, we could let $e_j$ be the expected number of moves to reach a type $10$ square from a type $j$ square, for $1 \le j \le 9$ . Conditional probability thinking tells us that $\begin{array}{rcl} e_1 & = & 1 + e_6 \\ e_2 & = & 1 + \tfrac13(e_3 + e_7 + e_8) \\ e_3 & = & 1 + \tfrac14(e_2 + e_6 + e_8 + e_9) \\ e_4 & = & 1 + \tfrac14(e_5 + e_6 + e_8 + e_9) \\ e_5 & = & 1 + \tfrac12(e_4 + e_9) \\ e_6 & = & 1 + \tfrac16(e_1 + e_3 + e_4 + e_7 + e_9) \\ e_7 & = & 1 + \tfrac16(e_2 + e_3 + e_6 + e_8 + e_9) \\ e_8 & = & 1 + \tfrac14(e_2 + e_4 + e_7) \\ e_9 & = & 1 + \tfrac18(e_3 + e_4 + e_5 + e_6 + e_7 + 2e_9) \end{array}$ Solving these equations, we can calculate the desired answer of $1 + \tfrac14(e_6 + e_7 + e_8 + e_9) \; =\; 1 + \frac14\left(\frac{57496}{5923} + \frac{55593}{5923} + \frac{52055}{5923} + \frac{59930}{5923}\right) \; = \; \frac{21}{2}$