Recurrence in Finite Closed Classes

Why Finiteness and Closure Force a Return

A chain may move around a class of states without ever leaving it. If the class is finite and each state can communicate with every other, then from any state there is a path back to a chosen target. Finiteness makes this observation stronger: there is a fixed bound on the path lengths and a positive lower bound on their probabilities. Repeated opportunities to use those paths rule out avoiding the target forever.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\in S\). A path from \(x\) to \(y\) is a finite sequence of transitions with positive probability; states \(x\) and \(y\) communicate if each can be reached from the other. A communicating class is a maximal set of mutually communicating states. It is closed if \(p_{xy}=0\) whenever \(x\) is in the class and \(y\) is outside it.

The closed-class condition means the chain stays in the class once it starts there. The communication condition supplies a route to each target. The theorem below combines those facts; it does not require positive probability of staying at the target in one step.

Proof. Let \(C\) be a finite closed communicating class and fix \(i\in C\). If \(C=\{i\}\), closure and the row-sum condition give \(p_{ii}=1\): there are no transitions from \(i\) to states outside \(C\), and \(i\) is the only state in \(C\). Thus \(T_i^+=1\) with probability \(1\).

Now suppose \(C\) contains at least two states. For each \(x\in C\setminus\{i\}\), communication gives a path from \(x\) to \(i\) of some positive length \(\ell_x\). Let \(r_x>0\) be the product of the transition probabilities along this path. Since \(C\setminus\{i\}\) is finite, the numbers \(L=\max_{x\ne i}\ell_x\) and \(\varepsilon=\min_{x\ne i}r_x\) are well defined, with \(L\ge1\) and \(\varepsilon>0\). From any \(x\ne i\), the probability of hitting \(i\) within the next \(L\) steps is at least \(\varepsilon\), because the chosen path reaches \(i\) in at most \(L\) steps.

Consider the chain started at \(i\). If it has not returned by time \(n\ge1\), then \(X_n\in C\setminus\{i\}\): closure keeps it in \(C\), and the event of no return excludes \(i\). The Markov property therefore gives, conditional on its history through time \(n\), probability at least \(\varepsilon\) of hitting \(i\) within the next \(L\) steps. Consequently, for every integer \(k\ge0\),

Indeed, the bound for \(k=0\) is \(\mathbb{P}_i(T_i^+>1)\le1\). If the chain has avoided return through time \(1+kL\), the conditional probability that it also avoids \(i\) for the next \(L\) steps is at most \(1-\varepsilon\). Multiplying this conditional bound gives the displayed inequality by induction. Since \(0<\varepsilon\le1\), its right-hand side tends to zero as \(k\) tends to infinity (and is zero for \(k\ge1\) if \(\varepsilon=1\)). The events \(\{T_i^+>1+kL\}\) decrease to \(\{T_i^+=\infty\}\), so continuity of probability for decreasing events gives \(\mathbb{P}_i(T_i^+=\infty)=0\). Thus \(i\) is recurrent. The choice of \(i\) was arbitrary, proving the claim for every state in \(C\). \(\square\)

What the Uniform Bound Says

The essential step is a uniform lower bound, not an identical route from every state. For a fixed target, each other state in the class may have its own path and path length. Because there are only finitely many starting states, the longest chosen path is still finite and the smallest of their positive path probabilities is still positive. At each block of \(L\) steps spent away from the target, the chain therefore has probability at least \(\varepsilon\) to reach it. The probability of avoiding it through \(k\) such blocks is bounded by a geometric sequence.

The first-return version needs one small adjustment: the chain starts at \(i\), so a path of length zero from \(i\) to itself cannot count as a return. The proof first considers time \(1\). If no return has occurred by then, the chain is at a different state of \(C\), where the uniform path bound applies. The singleton case is handled separately because there are no other states from which to choose paths.

Proof. Fix \(i\in C\). The proof of the theorem supplies a uniform positive chance to hit \(i\) within a bounded number of steps from each state other than \(i\). From \(i\), either the chain returns in one step or it moves to another state in \(C\); in the latter case, the same bound applies after that step. Thus, from any state in \(C\), the probability of avoiding \(i\) for \(k\) successive blocks of a sufficiently large fixed length is bounded by \((1-\delta)^k\) for some \(\delta>0\). This tends to zero, so the probability of avoiding \(i\) forever after any fixed time is zero. The event that \(i\) is visited only finitely often is contained in the union, over all integer times \(m\ge0\), of the events that \(i\) is never visited after time \(m\). Each of these events has probability zero, and a countable union of probability-zero events has probability zero. Hence \(i\) is visited infinitely often almost surely. Since \(C\) is finite, the same conclusion holds simultaneously for every \(i\in C\): the union of the finitely many exceptional probability-zero events still has probability zero. \(\square\)

Worked Examples

Recurrence Is Not Aperiodicity

Recurrence concerns whether a return eventually occurs; it does not say which return times are possible. In the deterministic three-state cycle, returns to state \(1\) occur at times \(3,6,9,\ldots\), so the greatest common divisor of the possible positive return times is \(3\). The state is recurrent but periodic. In the two-state example, state \(1\) can return at time \(1\), and state \(2\) can return at time \(1\); a positive one-step return makes the greatest common divisor of the possible return times equal to \(1\). Both states are recurrent, and these return-time patterns differ.

Common mistake. A self-loop is not necessary for recurrence. In the deterministic cycle, \(p_{11}=0\), so the calculation “\(p_{11}=0\), therefore state \(1\) is transient” is wrong: it checks only a return at time \(1\). The actual path is \(1\to2\to3\to1\), giving \(\mathbb{P}_1(T_1^+=3)=1\). To test recurrence, consider the probability of any finite positive-time return, not just the one-step transition back to the starting state.