[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$.[/step]

[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]