Probability · Markov chains and random walks · Hard
A king comes home
A king stands on a corner square of an otherwise empty 8 × 8 chessboard. On each move it steps to one of the squares that touch its own, along a side or at a corner, choosing uniformly at random among those on the board. What is the expected number of moves until it is first back on the corner where it started?
Answer and solution
Answer
140
Solution
The long-run share of a square is proportional to its number of neighbours, and the expected return time is one over that share.
The 4 corners have 3 neighbours each, the 24 other edge squares 5 and the 36 inner squares 8: a total of 12 + 120 + 288 = 420. The corner's long-run share is 3/420 = 1/140, so the expected return time is 140 moves.
Markov chains and random walks comes up in 4 firms' roundsCitadel Securities · D. E. Shaw · Jump Trading · +1
These 6 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.