Learn / Library / Probability

Grid walk to the center

ProbabilityHard

A token starts in a corner cell of a $3 \times 3$ grid. At each step it moves to a uniformly random cell that shares a side with its current cell, independently of the past. What is the expected number of steps until the token first reaches the center cell?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Group the cells by type: corner, edge, center. Write equations for the expected time from a corner and from an edge cell.

Solution

Let $C$ be the expected time from a corner and $E$ the expected time from an edge cell.
A corner has $2$ neighbors, both edge cells, so $C = 1 + E$ .
An edge cell has $3$ neighbors: the center and $2$ corners, so $E = 1 + (\frac{2}{3}) \times C$ .
Substituting gives $E = 1 + (\frac{2}{3}) \times (1 + E)$ , so $\frac{E}{3} = \frac{5}{3}$ and $E = 5$ .
Then $C = 1 + 5$ , which is $6$ .

Answer: $6$

Next question Back to the library