A knight finds its way home
A knight starts on a corner square of an otherwise empty chessboard. At every move it chooses one of its legal knight moves uniformly at random.
Find the expected number of moves until it first returns to the starting corner.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
This is a random walk on a graph: squares are vertices, and two squares are joined when a knight can move between them. In the long run, how often is the walk at a given square?
For a random walk on a connected graph, the long-run fraction of time spent at a vertex is its degree divided by the sum of all degrees. The expected return time is the inverse of that fraction.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. For a random walk on a graph, the stationary probability of a vertex is proportional to its degree, and the expected time to return to a vertex is one over its stationary probability. So we only need to count knight moves.
Step 1: stationary distribution. For a random walk on a connected graph, is stationary: the flow into is .
Step 2: count the edges. A knight move changes one coordinate by 1 and the other by 2. Moves of the form fit on the board in ways, and so do , and . So there are edges, and the degrees add up to .
Step 3: the corner. A knight in a corner has 2 legal moves, so .
Step 4: return time. The expected return time is (Kac's formula):
Remark. The same method gives a king's expected return time to a corner: the king's degrees add up to 420 and a corner has degree 3, so 140 moves.