Here is a well-known interview/code golf question: a knight is placed on a chess board. The knight chooses from its 8 possible moves uniformly at random. When it steps off the board it doesn’t move anymore. What is the probability that the knight is still on the board after steps?
We could calculate this directly but it’s more interesting to frame it as a Markov chain.
Calculation using the transition matrix
Model the chess board as the tuples .
Here are the valid moves and a helper function to check if a move is valid and if a cell is on the usual chessboard:
The valid states are all the on-board positions plus the immediate off-board positions:
Now we can set up the transition matrix.
We can visualise the transition graph using graphviz (full code here):
Oops! The corners aren’t connected to anything so we have 5 communicating classes (the 4 corners plus the rest). We never reach these nodes from any of the starting positions so we can get rid of them:
Here’s the new transition graph:
Intuitively, the knights problem is symmetric, and this graph is symmetric, so it’s likely that we’ve set things up correctly.
Let , , , be the positions of the knight. Then then probability of the knight moving from state to in steps is
So the probability of being on the board after steps, starting from , will be
where is the set of on-board states. This is easy to calculate using Numpy:
For this case we get probability .
Here are a few more calculations:
start: (0, 0) n: 0 Pr(on board): 1.0 start: (3, 3) n: 1 Pr(on board): 1.0 start: (0, 0) n: 1 Pr(on board): 0.25 start: (3, 3) n: 4 Pr(on board): 0.48291015625 start: (3, 3) n: 5 Pr(on board): 0.35565185546875 start: (3, 3) n: 100 Pr(on board): 5.730392258771815e-13
It’s always good to do a quick Monte Carlo simulation to sanity check our results:
The estimate is fairly close to the value we got from taking power of the transition matrix:
pr on board from (3,3) after 5 steps: 0.3554605
An absorbing state of a Markov chain is a state that, once entered, cannot be left. In our problem the absorbing states are precisely the off-board states.
A natural question is: given a starting location, how many steps (on average) will it take the knight to step off the board?
With a bit of matrix algebra we can get this from the transition matrix . Partition by the state type: let be the transitions of transient states (here, these are the on-board states to other on-board states); let be transitions from transient states to absorbing states (on-board to off-board); and let be the identity matrix (transitions of the absorbing states). Then can be written in block-matrix form:
We can calculate powers of :
We want to calculate since this will tell us the long-term probability of moving from one state to another. In particular, the top-right block will tell us the long-term probability of moving from a transient state to an absorbing state.
Here is a handy result from matrix algebra:
Lemma. Let be a square matrix with the property that as . Then
Applying this to the block form gives:
where since all of the entries in are transient.
The top-right corner also contains the fundamental matrix as defined in the following theorem:
Theorem Consider an absorbing Markov chain with transient states. Let be a matrix indexed by the transient states, where is the expected number of visits to given that the chain starts in . Then
Taking the row sums of gives the expected number of steps starting from state until absorption (i.e. we count the number of visits to each transient state before eventual absorption):
Back in our Python code, we can rearrange the states vector so that the transition matrix is appropriately partitioned. Taking the matrix is very quick using Numpy’s slicing notation:
Again, compare to a Monte Carlo simulation to verify that the numbers are correct:
start: (0, 0) Avg nr steps to absorb (MC): 1.9527606 start: (0, 0) Avg nr steps (F matrix): 1.9525249995183136 start: (3, 3) Avg nr steps to absorb (MC): 5.4187947 start: (3, 3) Avg nr steps (F matrix): 5.417750460813215
So, on average, if we start in the corner we will step off the board after steps; if we start in the centre at we will step off the board after steps.
The theoretical parts of this blog post follow the presentation in chapter 3 of Introduction to Stochastic Processes with R (Dobrow).