Fall 2011 Strategic Practice 11: Section 3 (Markov Chains) - Question 4
In chess, the king can move one square at a time in any direction (horizontally, vertically, or diagonally).
For example, in the diagram, from the current position the king can move to any of 8 possible squares. A king is wandering around on an otherwise empty 8 by 8 chessboard, where for each move all possibilities are equally likely. Find the stationary distribution of this chain (of course, don't list out a vector of length 64 explicitly! Classify the 64 squares into "types" and say what the stationary probability is for a square of each type).
Solution: Consult iTunes course for full detailed solutions. The stationary probabilities are proportional to the degrees. Each corner square has degree 3, each edge square has degree 5, and each normal square has degree 8. The total degree is 420 = 3 x 4 + 24 x 5 + 36 x 8 (which is also twice the number of edges in the network). Thus, the the stationary probability is 3/420 for a corner square, 5/420 for an edge square, and 8/420 for a normal square.
"Mathematics is the logic of certainty, but statistics is the logic of uncertainty."