What is the $\mathbb{P}(T_n<\infty)$ of a Markov chain on chess.

Question

Under the assumption of the below question:

Knight returning to corner on chessboard -- average number of steps

I have a similar question: assume that two knights begin on opposite squares (such as $h1, h8$) of the chessboard. What is the $$\mathbb{P}(T_n<\infty)$$ where $T_n:=\min\{n: L_n=Q_n\}$, $L_n$ and $Q_n$ are the position of these two knights.

Clearly, we need to see this problem as a simple random walk on a graph(finite, simple, connected). It is easy to compute the expectation of one Markov chain returns back. But how to describe $\min\{n: L_n=Q_n\}$?

Answer 1

$\mathbb P(T < \infty)$ is $\fbox{0}$.

Proof: You have a periodicity problem on your hands here. The knight the starts on H1 begins on a white square, and the knight that starts on H8 starts on a black square. On each step, both knights will switch what square color they occupy. Consequently, the knights will each occupy one white and one black square and will never overlap.

---

Now, let's do a version of the question that you didn't ask:

What if one knight starts at A1 and the other starts at H8?

In this case, $\mathbb P(T < \infty)$ is $\fbox{1}$. The short answer for why is: finite irreducible Markov chains visit every state infinitely often with probability 1.

Proof: As Ian suggested, the state space for the joint random walk can be regarded as $K \times K$, where $K$ is the spaces on a chessboard. Note that the walk cannot actually visit each state of $K \times K$; for instance, it isn't possible to visit the state (H1, H8) for the exact reasons I outlined in the earlier problem. However, there is some connected component of $K \times K$ which contains (A1, H8).

Claim: This connected component contains at least one element of the diagonal set $\Delta = \{(x, x) : x \in K\}$.

Proof: Consider the path (A1, H8) $\to$ (C2, F7) $\to$ (D4, E5) $\to$ (F3, F3) $\in \Delta$.

From here, we regard the random walk as being on $C \subset K \times K$, where $C$ is the connected component described above.

Claim: This Markov chain is finite and irreducible.

Proof: Finiteness is obvious; irreducibility comes for free because we are considering the connected component of $K \times K$ that contains (A1, H8).

Claim: The above imply that $\mathbb P(T < \infty) = 1$.

Sketch of proof: We know that there is some state $z \in \Delta \cap C$ by the above argument. Irreducibility implies that if the walk starts from any state, there is a positive probability of it traveling to $z$ in some finite number $n$ of steps. Because the chain is finite, we can place a universal upper bound $N$ on these numbers $n$ (across all states $x \in C$). Consequently, we can place a universal lower bound on $$\mathbb P_x(\text{the walk visits $z$ at some point within the next $N$ steps})$$ where the bound is placed across all $x \in C$. From here, we can break up the time interval into $[0, N-1], [N, 2N-1], [2N, 3N-1], \dots$ and bound the probability of never visiting $z$ above by some number $p < 1$. We can condition on never having done so in the past and use the Markov property to show that the chance of never doing so after $k$ intervals of this form is $p^k < 0$ as $k \to \infty$.

(NB: There are lots of ways to show this last claim, and I don't think I picked the cleanest one.)

---

Finally, one more version of the question that you didn't ask:

With the starting positions of A1 and H8, what is the expected time to meet?

Because the chain is finite and irreducible, ergodic theory implies that the expected time is finite. However, I don't know a clever way to find what the expectation is, and if I needed it, I'd use some computational methods (i.e. big matrix calculations) or Monte Carlo simulations.