Closed Classes Organize a Finite Chain
A finite Markov chain may contain several different long-run regions. Once the chain enters a closed communicating class, it cannot leave that class; states outside all such classes can be visited only transiently. The key classification is therefore structural: find the closed classes first, then identify the remaining states. A directed graph of positive transition probabilities makes this task visible.
Throughout, let \((X_n)_{n\ge0}\) be a time-homogeneous Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). We write \(\mathbb{P}_i\) when \(X_0=i\), and use \(T_i^+=\inf\{n\ge1:X_n=i\}\) for the first return time to \(i\). A state \(i\) is recurrent if \(\mathbb{P}_i(T_i^+<\infty)=1\), and transient if \(\mathbb{P}_i(T_i^+<\infty)<1\).
Communication does not by itself make a class closed: a chain may move between states in a class and still have a positive probability of leaving it. The finite irreducible-chain result established in the earlier material says that a finite irreducible chain is recurrent. Consequently, a finite closed communicating class is recurrent: restricting the chain to that class gives a finite irreducible chain, and closedness ensures that the restriction is a Markov chain.
The Finite-Chain Classification
The last assertion has a useful graph interpretation. Collapse each communicating class to a single vertex, keeping an arrow when there is a transition between two different classes. The resulting finite graph has no directed cycles: a cycle among distinct classes would make those classes communicate, contradicting their distinctness. A finite directed acyclic graph has a vertex with no outgoing edge. Such a vertex corresponds to a closed class. Following outgoing edges from any class must therefore eventually lead to a closed class.
Proof. First consider the directed graph whose vertices are the communicating classes and whose edges record transitions between distinct classes. If this graph contained a directed cycle, each class on the cycle could reach every other class on the cycle. The states in those classes would then communicate, so they would belong to a single communicating class. Thus the graph has no directed cycles. Starting at any vertex and following an outgoing edge whenever one exists must terminate, because the graph is finite and has no directed cycles. The terminal vertex has no outgoing edge, so its class is closed. The edges along this route come from positive transition probabilities; within each communicating class, the states on the route can be connected by positive-probability paths. Hence each state has a path to a closed class.
Let \(C\) be the union of all closed communicating classes, and let \(B=S\setminus C\). Once the chain enters \(C\), it stays in \(C\), because each class in the union is closed. For each \(x\in B\), choose a positive-probability path from \(x\) to \(C\), as established above. Let its length be \(n_x\ge1\) and its probability be \(a_x>0\), the product of the transition probabilities along that path. Since \(B\) is finite, if \(B\) is nonempty we may set \(N=\max_{x\in B}n_x\) and \(\varepsilon=\min_{x\in B}a_x>0\). For every \(x\in B\), the probability of entering \(C\) within the next \(N\) steps is at least \(a_x\), and therefore at least \(\varepsilon\).
By the Markov property, conditional on still being in \(B\) after \(kN\) steps, the probability of remaining in \(B\) for the next \(N\) steps is at most \(1-\varepsilon\). Since \(C\) cannot be left, for every initial state \(x\) and integer \(k\ge0\), \(\mathbb{P}_x(X_{kN}\in B)\le(1-\varepsilon)^k\). For \(kN\le n<(k+1)N\), the event \(X_n\in B\) implies \(X_{kN}\in B\), because entry into \(C\) is permanent. Therefore \[ \sum_{n\ge0}\mathbb{P}_x(X_n\in B) \le N\sum_{k\ge0}(1-\varepsilon)^k =\frac{N}{\varepsilon}<\infty. \] In particular, for any \(i\in B\), starting from \(i\), the expected total number of visits to \(i\) is finite: \(\sum_{n\ge0}p_{ii}^{(n)}\le N/\varepsilon\). By the return-series criterion established in the earlier material, finiteness of this series implies that \(i\) is transient. If \(B\) is empty, there are no states to classify outside \(C\). Finally, every state in a closed class is recurrent by the finite irreducible-chain result stated above. This proves the classification. \(\square\)
The proof supplies more than a label for each state. It shows that the probability of still being outside all closed classes decreases geometrically when time is examined in blocks of \(N\) steps. Thus the expected total number of visits to the union of the nonclosed classes is finite. No assumption of aperiodicity is needed: the conclusion concerns recurrence and transience, not convergence of the distribution at a fixed time.
Using the Transition Graph
A practical classification can be done in three steps. First, list the directed edges \(i\to j\) for which \(p_{ij}>0\). Second, group states that can reach each other into communicating classes. Third, inspect each class for outgoing edges: a class is closed exactly when there are none. The theorem then classifies every state not in those closed classes as transient.
Worked Example: One Closed Class and Two Transient States
Consider \(S=\{1,2,3\}\) with transition matrix \[ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 0&0&1 \end{bmatrix}. \] The row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+0+1=1\), so this is a transition matrix.
There are edges \(1\to2\), \(2\to1\), \(2\to3\), and \(3\to3\). States \(1\) and \(2\) communicate, but their class is not closed because \(p_{23}=\tfrac12>0\). The class \(\{3\}\) is closed. The theorem therefore classifies \(1\) and \(2\) as transient and \(3\) as recurrent.
Check by return probabilities. Starting at \(1\), the chain must move to \(2\). It next returns to \(1\) with probability \(\tfrac12\), and moves to \(3\) with probability \(\tfrac12\); after reaching \(3\), it cannot return to \(1\). Hence \(\mathbb{P}_1(T_1^+<\infty)=\tfrac12<1\). Starting at \(2\), the chain returns to \(2\) if it first moves to \(1\), which has probability \(\tfrac12\), since \(1\to2\) with probability \(1\). If it instead moves to \(3\), it never returns. Thus \(\mathbb{P}_2(T_2^+<\infty)=\tfrac12<1\), confirming both states are transient.
Worked Example: Two Closed Classes with Different Destinations
Let \(S=\{1,2,3,4\}\) and \[ P=\begin{bmatrix} 0&\tfrac13&\tfrac23&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{bmatrix}. \] The row sums are \(0+\tfrac13+\tfrac23+0=1\), \(0+1+0+0=1\), \(0+0+0+1=1\), and \(0+0+1+0=1\). The class \(\{2\}\) is closed, and \(\{3,4\}\) is a closed communicating class because \(3\to4\) and \(4\to3\), with no transitions out of the pair. State \(1\) is a singleton communicating class but is not closed.
From state \(1\), the chain enters \(\{2\}\) in one step with probability \(\tfrac13\), or enters \(\{3,4\}\) in one step with probability \(\tfrac23\). These probabilities add to \(\tfrac13+\tfrac23=1\). State \(1\) has no transition back to itself, so \(\mathbb{P}_1(T_1^+<\infty)=0\); it is transient. The closed classes are recurrent by the theorem, even though the motion within \(\{3,4\}\) alternates between its two states.
Check the destinations. The probability of eventually entering \(\{2\}\) is exactly the one-step probability \(\tfrac13\), because state \(2\) is absorbing. The probability of eventually entering \(\{3,4\}\) is exactly \(\tfrac23\), because either state in that class remains in it. These probabilities sum to \(1\), as required.
Worked Example: A Transient Communicating Class
Consider \[ P=\begin{bmatrix} 0&\tfrac12&\tfrac12&0\\ \tfrac12&0&0&\tfrac12\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix} \quad\text{on }S=\{1,2,3,4\}. \] Its row sums are \(0+\tfrac12+\tfrac12+0=1\), \(\tfrac12+0+0+\tfrac12=1\), \(0+0+1+0=1\), and \(0+0+0+1=1\). States \(1\) and \(2\) communicate, but their class is not closed: state \(1\) can move to \(3\), and state \(2\) can move to \(4\). The singleton classes \(\{3\}\) and \(\{4\}\) are closed. Therefore \(1\) and \(2\) are transient.
The transient classification can also be checked from the probability of remaining in \(\{1,2\}\). From either state in that pair, the probability of staying in the pair for one more step is \(\tfrac12\). Conditional on remaining there, the same probability applies at the next step. Thus the probability of still being in \(\{1,2\}\) at time \(n\), starting in either state, is \((\tfrac12)^n\). Summing over \(n\ge0\), the expected number of time indices spent in the pair is \[ \sum_{n\ge0}\left(\tfrac12\right)^n =\frac{1}{1-\tfrac12}=2. \] In particular, each state has finite expected visits and is transient.
Check a return probability. Starting at \(1\), a first return can occur only by moving to \(2\) and then to \(1\). The probability of this two-step path is \(\tfrac12\cdot\tfrac12=\tfrac14\). Any move from \(1\) to \(3\), or from \(2\) to \(4\), makes a return impossible. Hence \(\mathbb{P}_1(T_1^+<\infty)=\tfrac14<1\). By the same calculation, \(\mathbb{P}_2(T_2^+<\infty)=\tfrac14<1\).
Common Pitfall: Communication Is Not Closedness
A common error is to see that two states communicate and conclude that they are recurrent. In the first example, \(1\leftrightarrow2\), but the positive-probability transition \(2\to3\) leaves their class permanently. Treating only transitions internal to \(\{1,2\}\) and saying their total probability is \(1\) would incorrectly classify them as recurrent. The actual row from state \(2\) assigns probability \(\tfrac12\) to state \(3\); the first-return calculation gives \(\mathbb{P}_1(T_1^+<\infty)=\tfrac12\), not \(1\). The correction is to check every outgoing transition from every state in a class. Only if all transitions remain in the class is it closed.
For finite chains, the classification is complete once the closed communicating classes are identified: those classes are recurrent, and all states outside them are transient. This does not assert that the distribution of \(X_n\) converges, nor does it compare mean return times; those are separate questions. The classification concerns whether a state is revisited with probability one, and the graph of positive transitions determines the answer.
Check Your Understanding
For each question, distinguish communication from closedness and use strict inequalities when deciding whether a return probability is less than \(1\).
- In the first worked example, why is \(\{1,2\}\) a communicating class but not a closed class?
- A finite chain has communicating classes \(\{a,b\}\), \(\{c\}\), and \(\{d\}\), with \(\{c\}\) and \(\{d\}\) closed. What does the classification theorem imply about state \(a\) and state \(b\)?
- For the second example, compute the probability from state \(1\) of eventually entering \(\{3,4\}\). Why does no additional multi-step calculation change the answer?
- Explain why a directed cycle among distinct communicating classes is impossible.
- In the third example, verify the probability of remaining in \(\{1,2\}\) for exactly \(n\) steps, and use its sum over \(n\ge0\) to check transience.