3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Please include more details: the source of the question, why it interests you, your thoughts on it, what your tried, or where you're stuck. What have you learned that you think might apply to solving this question? E.g., $\endgroup$
    – amWhy
    Commented Aug 21, 2020 at 16:58
  • 1
    $\begingroup$ @amWhy Such questions are hard to answer because 1) They are related to competitions (the OP has mentionned HMMT) 2) The level of knowledge of the OP is unknown. After some hesitation, I have decided to give him/her a (big) hint in order that he/she at least can better identify the domain addressed by this question... $\endgroup$
    – Jean Marie
    Commented Aug 22, 2020 at 8:13

1 Answer 1

5
$\begingroup$

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):

enter image description here

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .