[proofplan] We show that every state $i$ hits $j$ with probability one by exploiting the recurrence of $j$ and irreducibility. Since $j \to i$, there exists a path of minimal length from $j$ to $i$; minimality forces this path to avoid $j$ at intermediate times, which lets us bound the probability of never reaching $j$ from $i$ in terms of the probability that $j$ never returns to itself. Since $j$ is recurrent, this latter probability is zero, forcing $f_{i,j} = 1$ for every $i$. The result for a general initial distribution then follows by averaging over the starting state. [/proofplan] [step:Show that $\mathbb{P}_i(X_n = j \text{ for some } n \geq 1) = 1$ for every $i \in S$] Define the hitting probability \begin{align*} f_{i,j} := \mathbb{P}_i(X_n = j \text{ for some } n \geq 1). \end{align*} We must show $f_{i,j} = 1$ for every $i \in S$. Since the chain is irreducible, $j \to i$. Choose the least integer $m \geq 1$ such that $p_{j,i}(m) > 0$. The minimality of $m$ ensures that the path from $j$ to $i$ in $m$ steps cannot visit $j$ at any intermediate time $r \in \{1, \ldots, m-1\}$: if the chain visited $j$ at some intermediate time $r < m$, then $p_{j,i}(m - r) > 0$ with $m - r < m$, contradicting the minimality of $m$. Therefore \begin{align*} p_{j,i}(m) = \mathbb{P}_j(X_m = i,\; X_r \neqeq j \text{ for } 1 \leq r \leq m-1). \end{align*} Consider the event $A = \{X_m = i\} \cap \{X_r \neqeq j \text{ for } 1 \leq r \leq m-1\} \cap \{X_n \neqeq j \text{ for all } n \geq m+1\}$, starting from $j$. On this event, the chain starts at $j$, reaches $i$ at time $m$ without revisiting $j$ in between, and then never visits $j$ again after time $m$. By the [Strong Markov Property](/theorems/2208), the probability of the third sub-event conditional on $X_m = i$ is $1 - f_{i,j}$, independently of the trajectory up to time $m$. Therefore \begin{align*} \mathbb{P}_j(A) = \mathbb{P}_j(X_m = i,\; X_r \neqeq j \text{ for } 1 \leq r \leq m-1) \cdot (1 - f_{i,j}) = p_{j,i}(m)(1 - f_{i,j}). \end{align*} The event $A$ is contained in $\{X_n \neqeq j \text{ for all } n \geq 1\}$ (starting from $j$), whose probability is $1 - f_{j,j}$. Hence \begin{align*} p_{j,i}(m)(1 - f_{i,j}) \leq 1 - f_{j,j}. \end{align*} Since $j$ is recurrent, $f_{j,j} = 1$, so the right-hand side equals $0$. Since $p_{j,i}(m) > 0$, we conclude $1 - f_{i,j} = 0$, i.e., $f_{i,j} = 1$. [guided] We want to show that every starting state $i$ eventually reaches $j$ with probability $1$. The idea is to argue by contradiction: if there were a positive probability of never reaching $j$ from some state $i$, we could use this to construct a positive probability of the chain starting at $j$ and never returning to $j$, violating recurrence. Define the hitting probability \begin{align*} f_{i,j} := \mathbb{P}_i(X_n = j \text{ for some } n \geq 1). \end{align*} We must show $f_{i,j} = 1$ for every $i \in S$. Since the chain is irreducible, $j \to i$. Among all integers $n \geq 1$ with $p_{j,i}(n) > 0$, choose the smallest; call it $m$. Why does minimality matter? Because it forces the chain to avoid $j$ at intermediate times. If the chain visited $j$ at some intermediate time $r \in \{1, \ldots, m-1\}$, then by the [Chapman--Kolmogorov Equations](/theorems/2207), $p_{j,i}(m - r) \geq p_{j,j}(r) \cdot p_{j,i}(m-r)$, and more directly, the existence of a path from $j$ to $j$ to $i$ in $r + (m-r) = m$ steps that passes through $j$ at time $r$ would mean $p_{j,i}(m-r) > 0$ with $m - r < m$, contradicting the minimality of $m$. Therefore the entire $m$-step probability $p_{j,i}(m)$ is concentrated on paths that avoid $j$ at intermediate times: \begin{align*} p_{j,i}(m) = \mathbb{P}_j(X_m = i,\; X_r \neqeq j \text{ for } 1 \leq r \leq m-1). \end{align*} Now consider starting at $j$, reaching $i$ at time $m$ (while avoiding $j$), and then never visiting $j$ again. By the [Strong Markov Property](/theorems/2208), conditional on $X_m = i$, the future evolution after time $m$ is an independent copy of the chain started at $i$, so the probability of never reaching $j$ from time $m$ onward is exactly $1 - f_{i,j}$. Hence the probability of this combined event is \begin{align*} \mathbb{P}_j(A) = p_{j,i}(m)(1 - f_{i,j}). \end{align*} The event $A$ is contained in the event that the chain, starting from $j$, never returns to $j$ (since $j$ is not visited at intermediate times $1, \ldots, m-1$, and not visited after time $m$ either). The probability of never returning to $j$ from $j$ is $1 - f_{j,j}$. Therefore \begin{align*} p_{j,i}(m)(1 - f_{i,j}) \leq 1 - f_{j,j}. \end{align*} Since $j$ is recurrent, $f_{j,j} = 1$ by the definition of recurrence, so the right-hand side is $0$. Since $p_{j,i}(m) > 0$ (by construction), we must have $1 - f_{i,j} = 0$, giving $f_{i,j} = 1$. What would fail without recurrence? If $j$ were transient, then $1 - f_{j,j} > 0$, and the inequality would only give $1 - f_{i,j} \leq (1 - f_{j,j}) / p_{j,i}(m)$, which does not force $f_{i,j} = 1$. The recurrence hypothesis is essential. [/guided] [/step] [step:Average over the initial distribution to conclude the result] Let $\lambda = (\lambda_i : i \in S)$ be any initial distribution for the chain. By the law of total probability, conditioning on the starting state $X_0$: \begin{align*} \mathbb{P}(X_n = j \text{ for some } n \geq 1) &= \sum_{i \in S} \lambda_i \, \mathbb{P}_i(X_n = j \text{ for some } n \geq 1) = \sum_{i \in S} \lambda_i \cdot 1 = 1, \end{align*} where we used $f_{i,j} = 1$ for every $i \in S$ (established in the previous step) and $\sum_{i \in S} \lambda_i = 1$. [/step]