Classifying Communicating Classes by Recurrence

How a Communicating Class Gets Its Type

A communicating class can contain many states, but its recurrence classification does not depend on which state is chosen. This is useful because the class may be infinite: finiteness alone cannot determine whether a return is certain or how many visits to expect. Instead, the relevant quantities are the probability of returning to a state and the sum of its return probabilities over time. Closedness gives additional information: every recurrent communicating class is closed, but an infinite closed class need not be recurrent.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Its rows sum to \(1\), and \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)\). States \(i\) and \(j\) communicate, written \(i\leftrightarrow j\), if each can be reached from the other in finitely many steps with positive probability. A communicating class is an equivalence class under this relation. The class \(C\) is closed if \(p_{ij}=0\) for every \(i\in C\) and \(j\notin C\).

These definitions apply to countable state spaces, not just finite ones. In particular, recurrence means that a return occurs eventually with probability \(1\); it does not mean that the expected time until return is finite.

Return Probability and Expected Visits

Proof. Start the chain at \(i\), and let \(V_i=\sum_{n\ge0}\mathbf{1}_{\{X_n=i\}}\) be its total number of visits to \(i\). The number of visits includes the visit at time \(0\). Thus, for each integer \(k\ge1\), the event \(V_i\ge k\) is the event that at least \(k-1\) returns occur. At each return, the chain starts afresh from \(i\): this follows from the Markov property by conditioning on each possible finite return time and the path up to that time. Repeating this argument gives \(\mathbb{P}_i(V_i\ge k)=f_i^{\,k-1}\). For a positive integer-valued random variable, possibly infinite, its expectation equals \(\sum_{k\ge1}\mathbb{P}(V_i\ge k)\); this follows by writing \(V_i=\sum_{k\ge1}\mathbf{1}_{\{V_i\ge k\}}\) and taking expectations of increasing partial sums. Therefore \(G_i=\mathbb{E}_i[V_i]=\sum_{k\ge1}f_i^{\,k-1}\). This geometric series equals \(1/(1-f_i)\) for \(f_i<1\), and diverges for \(f_i=1\). Also, \(\mathbb{E}_i[V_i]=\sum_{n\ge0}\mathbb{P}_i(X_n=i)=\sum_{n\ge0}p_{ii}^{(n)}\), by the same increasing-sums argument. The claimed equivalences follow. \(\square\)

This identity translates a question about eventual return into one about all \(n\)-step return probabilities. The classification does not require the terms \(p_{ii}^{(n)}\) to be computed in closed form: it is enough to determine whether their sum is finite.

Recurrence Type Is Shared Within a Class

Proof. Suppose \(i\leftrightarrow j\). There are positive integers \(r,s\) such that \(p_{ij}^{(r)}>0\) and \(p_{ji}^{(s)}>0\). Chapman–Kolmogorov, with the intermediate states \(i\) and \(j\) selected in the sum, gives, for every \(n\ge0\),

The constant \(c=p_{ji}^{(s)}p_{ij}^{(r)}\) is positive. Summing the inequality over \(n\ge0\) shows that if \(G_i=\infty\), then \(G_j=\infty\), since the left side is a subseries of \(G_j\) and is at least \(cG_i\). Interchanging \(i\) and \(j\) gives the reverse implication. Thus \(G_i\) is infinite exactly when \(G_j\) is infinite; it is finite exactly when \(G_j\) is finite. By the return-probability and visit-sum theorem, the two states have the same recurrence type. Since this holds for every pair in the class, the whole class has one type. \(\square\)

The theorem gives a direct classification procedure: choose any representative state in a communicating class, determine whether its return probability is \(1\), or equivalently whether its expected visit sum diverges, and assign that type to the entire class. This remains valid when the class is infinite.

What Closedness Does—and Does Not—Tell You

Proof. Let \(C\) be a recurrent communicating class, and take \(i\in C\). By the class theorem, \(i\) is recurrent. Suppose there were a state \(k\notin C\) with \(p_{ik}>0\). If \(k\) could reach \(i\) with positive probability in finitely many steps, then \(i\) could reach \(k\) in one step and \(k\) could reach \(i\); this would imply \(k\leftrightarrow i\), contradicting \(k\notin C\). Therefore \(\mathbb{P}_k(T_i<\infty)=0\), where \(T_i=\inf\{n\ge0:X_n=i\}\). Starting from \(i\), a first step to \(k\) makes a return to \(i\) impossible. The probability of that first step is positive, so \(f_i<1\), contradicting recurrence. Hence no such transition exists. Applying this argument to every \(i\in C\) proves that \(C\) is closed. \(\square\)

The reverse implication fails for infinite classes, as the preceding biased random walk demonstrates. Closedness rules out transitions to other classes; it does not decide whether a state inside the class will return. The return probability or visit sum supplies that missing information.

Common Classification Errors

A common mistake is to treat closedness as a recurrence test. In the biased random walk example, the entire state space is a closed irreducible class, but its return probability is \(2/3\), not \(1\). The correct calculation is \(f_0=(2/3)(1/2)+(1/3)(1)=2/3\), which classifies the class as transient. Calling it recurrent merely because it is closed confuses “cannot leave the class” with “returns to a particular state with probability one.”

A second mistake is to decide the class type from a single state's apparent behavior without checking communication. The class theorem requires mutual communication; if two states lie in different classes, their recurrence types need not agree, as the two-state example shows. Conversely, once mutual communication is established, the theorem guarantees that one representative's return classification applies throughout that class.

For an infinite state space, do not infer that recurrence entails a finite expected return time. Recurrence is the condition \(f_i=1\); the expected visit sum is then infinite. The expected number of time steps until return is a different quantity and requires separate analysis.