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?
 A: You can solve using transition probability matrix.
$\begin{bmatrix} C_1 & C_2 & C_3 \\ C_4 & C_5 & C_6 \\ C_7 & C_8 & C_9 \\\end{bmatrix}$ 
Construct Transition probability matrix, using the probability of one cell to another. Eg: $P[C_1, C_2] = P[C_1, C_4]= P[C_1, C_5] = \frac{1}{3}$. 
P will be a $9 \times 9$ matrix. 
Now you can calculate stationary probabilities (Since all states are recurrent).
Solve $\pi P = \pi $ such that $\sum \pi =1$.
This gives the probability of one king in particular square as n large.
Use the independence property you can arrive at the required probability.
A: 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:

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}.$$
A: Since the two kings are moving independently, you can consider them separately. If the board is of finite size, and doesn't have any closed subsections, this is one of those cases where the stationary distribution can be found by solving the detailed balance equation.
In this case, as $n$ goes to infinity, the probability of a king being in a square becomes proportional to the number of squares adjacent to it, i.e. three for each corner square, five for each edge square, and eight for the middle square. This sums to $40$, so the chance of being in the middle square is $8/40$, in any corner square is $3/40$, and in any edge square is $5/40$.
Since this is true for both kings independently, the chance of them both being in the middle square is $(8/40)^2 = 64/1600$, of both being in any corner square is $(3/40)^2=9/1600$, and in any edge square is $(5/40)^2=25/1600$. So the chance of them being in the same square approaches $\frac{64+4\times9+4\times25}{1600} = \frac{200}{1600} = \frac{1}{8}$ as $n$ approaches infinity.
