Random walk: kings on a chessboard

I have a question about the random walk of two kings in a 3×3 chessboard.

Each king is moving randomly with equal probability on this chessboard – vertically, horizontally and diagonally. Τhe two kings are moving independently from each other in the same chessboard. Both of them start in the same square, and then they move independently.

How could we find the probability in time n both of them are in the same square, as n goes to infinity?

Answer

Let’s exploit the symmetry to simplify the calculations.

The chessboard and its moves remain the same when the board is reflected vertically, horizontally, or diagonally. This decomposes its nine squares into three types, their orbits under this symmetry group. Correspondingly, each king can be in one of three “states”: a corner square (C), an edge square (E), or the central (“middle”) square (M). (A state ignores which particular square a king is on and tracks only its equivalence class under the group of symmetries.)

The following results are immediate:

  • From a corner square, there are two transitions to edge squares and one transition to a middle square. Because the three transitions are equiprobable,

    \Pr(C \to E) = 2/3,\quad \Pr(C \to M) = 1/3.

    This gives a row (0, 2/3, 1/3) in a transition matrix for the states (C, E, M).

  • From an edge square there are two transitions to corner squares, two to other edge squares, and one to the middle square. This gives a second row (2/5, 2/5, 1/5) in a transition matrix.

  • From the middle square there are four transitions to corner squares and four to middle squares. The third row of a transition matrix therefore is (4/8, 4/8, 0) = (1/2, 1/2, 0).

In this graph representing this Markov chain, transition probabilities are represented both by edge thickness and color:

Figure

By inspection or otherwise, we find that a left eigenvector of its transition matrix

\mathbb{P} = \left(
\begin{array}{ccc}
0 & \frac{2}{3} & \frac{1}{3} \\
\frac{2}{5} & \frac{2}{5} & \frac{1}{5} \\
\frac{1}{2} & \frac{1}{2} & 0 \\
\end{array}
\right)

is \omega = (3, 5, 2)^\prime. This claim is easily checked by performing the multiplication: \omega \mathbb{P} = 1 \omega. The eigenvalue manifestly is 1. Because all states are connected, \omega gives the limiting probabilities of each king being in each state; we only need to rescale its components to sum to unity:

\omega = (\omega_C, \omega_E, \omega_M) = (3/10, 5/10, 2/10).

(This is where we reap the benefits of exploiting the symmetry: instead of working with a nine by nine matrix of 81 elements we only have to compute with a three by three matrix of 9 elements. The reduction of the problem from nine states to three paid off quadratically by reducing the computational effort by a factor of (9/3)^2 = 9.)

The (limiting) chance that both kings are in a state s of (limiting) probability \omega_s is \omega_s^2 because the kings move independently. The chance that both kings are in the same cell is found by conditioning on the state: by symmetry, each cell in a given state has the same limiting probability, so if both kings are found in a state s having k_s cells, the chance they are both in the same cell is 1/k_s. Whence the solution is

\sum_{s\in \{C,E,M\}}\frac{ \omega_s^2 }{k_s} = \left(\frac{3}{10}\right)^2\frac{1}{4} + \left(\frac{5}{10}\right)^2\frac{1}{4} + \left(\frac{2}{10}\right)^2\frac{1}{1} = \frac{9}{400} + \frac{25}{400} + \frac{16}{400} = \frac{1}{8}.

Attribution
Source : Link , Question Author : cube , Answer Author : whuber

Leave a Comment