Consider an 8 × 8 grid of squares. A rook is placed in the lower left corner, and every minute it moves to a square in the same row or column with equal probability (the rook must move; i.e. it cannot stay in the same square). What is the expected number of minutes until the rook reaches the upper right corner?
Source: HMMT
Other:
I suspect this involves states but am not sure how to go about solving it.
Edit: Thank you, however, I don't understand why the denominator is 14. Could anyone please explain?
Consider 4 "states":
State S: Starting state.
State 1: being in the $7 \times 7$ lower left part of the checkerboard.
State 2: being on one of the top or right borders but not in the top right cell.
State 3: being "arrived" at this upper right cell.
The transitions between these states and the associated probabilities are featured on the right of the following image (for explanations see remark 4 at the bottom):
How can we use this so-called finite state Markov chain to obtain the mathematical expectation of random variable $T$, otherwise said the "Arrival time" ?
This document gives (page 6) a (classical) method using the transition probabilities matrix:
$$A=\left(\begin{array}{cc|c}6/7&1/7&0\\ 1/2&3/7&1/14\\ \hline 0&0&1\end{array}\right)$$
This method amounts to "extract" the $2 \times 2$ upper left block of $A$, call it $B$, then to compute
$$C:=(I_2-B)^{-1}=\begin{pmatrix}56&14\\49&14\end{pmatrix}.$$
and finally to add the entries of the first line, giving:
$$\mathbb{E}(T)=70 \ \text{minutes}.$$
Remark 1: I saw, a day after I wrote this answer, that this question had already been asked here but the method of solution of the unique valuable answer is different.
Remark 2: Please note that the "S" state and state 1 have been gathered.
Remark 3: For a broader view, see this excellent (online) book.
Remark 4: Explanations about probabilities $6/7, ...1/14$.
The sum of probabilities issued from any state, in particular state 2, is 1, Therefore, let us understand the two other probabilities For 1/2, it is immediate: for example if the rook is on the last column, one has first to select a direction (probability 1/2 to take horizontal direction) then one of the 7 possible moves in this direction, all of them being in the blue area. If, on the contrary, the vertical direction is chosen (the other 1/2 prob.)... 6 out of 7 moves keep the rook in the same (red) region.