[proofplan]
We verify the three properties of an equivalence relation. Reflexivity follows from $p_{i,i}(0) = 1 > 0$, and symmetry is built into the definition of $\leftrightarrow$. For transitivity, we use the [Chapman--Kolmogorov Equations](/theorems/2207) to lower-bound the $(m+n)$-step transition probability $p_{i,k}(m+n)$ by isolating the single term corresponding to the intermediate state $j$, then apply the same argument in reverse to establish the return direction.
[/proofplan]
[step:Verify reflexivity and symmetry]
**Reflexivity.** For any state $i \in S$, we have $p_{i,i}(0) = \mathbb{P}(X_0 = i \mid X_0 = i) = 1 > 0$, so $i \to i$. Since both directions hold, $i \leftrightarrow i$.
**Symmetry.** By definition, $i \leftrightarrow j$ means $i \to j$ and $j \to i$. This is symmetric in $i$ and $j$, so $i \leftrightarrow j$ implies $j \leftrightarrow i$.
[/step]
[step:Prove transitivity using the Chapman--Kolmogorov equations]
Suppose $i \leftrightarrow j$ and $j \leftrightarrow k$. We must show $i \leftrightarrow k$, which requires establishing both $i \to k$ and $k \to i$.
**Forward direction ($i \to k$).** Since $i \to j$, there exists $m \geq 0$ with $p_{i,j}(m) > 0$. Since $j \to k$, there exists $n \geq 0$ with $p_{j,k}(n) > 0$. By the [Chapman--Kolmogorov Equations](/theorems/2207):
\begin{align*}
p_{i,k}(m+n) = \sum_{r \in S} p_{i,r}(m)\, p_{r,k}(n) \geq p_{i,j}(m)\, p_{j,k}(n) > 0.
\end{align*}
The inequality holds because every term in the sum is non-negative (each $p_{i,r}(m)$ and $p_{r,k}(n)$ is a probability), so the full sum is at least as large as the single term with $r = j$. Since $p_{i,j}(m) > 0$ and $p_{j,k}(n) > 0$, the product is strictly positive. Hence $i \to k$.
**Reverse direction ($k \to i$).** Since $k \leftrightarrow j$, we have $k \to j$; choose $n' \geq 0$ with $p_{k,j}(n') > 0$. Since $j \leftrightarrow i$, we have $j \to i$; choose $m' \geq 0$ with $p_{j,i}(m') > 0$. By the same Chapman--Kolmogorov argument:
\begin{align*}
p_{k,i}(n'+m') = \sum_{r \in S} p_{k,r}(n')\, p_{r,i}(m') \geq p_{k,j}(n')\, p_{j,i}(m') > 0.
\end{align*}
Hence $k \to i$.
Since both $i \to k$ and $k \to i$ hold, we conclude $i \leftrightarrow k$. This establishes transitivity and completes the proof that $\leftrightarrow$ is an equivalence relation on $S$.
[guided]
Suppose $i \leftrightarrow j$ and $j \leftrightarrow k$. We need to show $i \leftrightarrow k$, which means both $i \to k$ and $k \to i$.
**Forward direction ($i \to k$).** The assumption $i \leftrightarrow j$ gives $i \to j$: there exists $m \geq 0$ with $p_{i,j}(m) > 0$. The assumption $j \leftrightarrow k$ gives $j \to k$: there exists $n \geq 0$ with $p_{j,k}(n) > 0$. Intuitively, the chain can go from $i$ to $j$ in $m$ steps, then from $j$ to $k$ in $n$ steps, so it should be able to go from $i$ to $k$ in $m + n$ steps. The [Chapman--Kolmogorov Equations](/theorems/2207) make this precise:
\begin{align*}
p_{i,k}(m+n) = \sum_{r \in S} p_{i,r}(m)\, p_{r,k}(n).
\end{align*}
This sum runs over all possible intermediate states $r$ at time $m$. Every term is non-negative (as a product of probabilities), so the sum is bounded below by any single term. Taking $r = j$:
\begin{align*}
p_{i,k}(m+n) \geq p_{i,j}(m)\, p_{j,k}(n) > 0.
\end{align*}
The strict positivity follows because both factors are strictly positive by construction. This shows $i \to k$.
**Reverse direction ($k \to i$).** We apply exactly the same argument, but using the reverse directions from the hypotheses. From $j \leftrightarrow k$, we extract $k \to j$: choose $n' \geq 0$ with $p_{k,j}(n') > 0$. From $i \leftrightarrow j$, we extract $j \to i$: choose $m' \geq 0$ with $p_{j,i}(m') > 0$. The Chapman--Kolmogorov equation gives:
\begin{align*}
p_{k,i}(n'+m') \geq p_{k,j}(n')\, p_{j,i}(m') > 0,
\end{align*}
so $k \to i$.
Combining both directions, $i \leftrightarrow k$. Note that the intermediate state $j$ plays a purely auxiliary role: it provides the "bridge" between $i$ and $k$, but the conclusion $i \leftrightarrow k$ is independent of $j$. This is exactly the content of transitivity.
[/guided]
[/step]
