From a Transition Matrix to Closed Classes
A finite transition matrix contains two kinds of information relevant to closed classes: which states can reach one another, and whether a transition can leave a group of mutually reachable states. The first question involves paths, which may take several steps; the second can be decided by checking the one-step probabilities leaving each class. Keeping these tasks separate makes classification systematic and helps prevent a common error: treating every nonzero-looking position, rather than every positive entry, as a possible transition.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite, nonempty state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Write its transition matrix as \(P=(p_{ij})\), where \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\in S\). In this tutorial, a directed edge \(i\to j\) means exactly that \(p_{ij}>0\).
The \(n\)-step transition formula explains the graph interpretation: \(p_{ij}^{(n)}\) is a sum, over length-\(n\) paths from \(i\) to \(j\), of products of the transition probabilities along those paths. Since each product is nonnegative, \(p_{ij}^{(n)}>0\) precisely when at least one such path has all its transition probabilities positive. A path of length zero allows a state to be accessible from itself. The earlier material on communication establishes that communication is an equivalence relation, so its classes partition \(S\).
A Reliable Identification Procedure
For an exact finite matrix, the work can be organized into three stages. First, check that each row sums to \(1\); this confirms that the given matrix can serve as a transition matrix. Second, keep precisely the directed edges corresponding to positive entries, and use paths in that graph to find the communicating classes. Third, for each class \(C\), inspect every row indexed by a state in \(C\): the class is closed exactly when all entries in columns outside \(C\) are zero. A single positive entry to an outside state is enough to show that the class is not closed.
This procedure does not require computing powers of the whole matrix. Path reasoning is used to form the classes, and the closure test uses only the original matrix entries. In particular, a class is not closed just because its states communicate with one another: it may also have transitions to other classes.
Proof. Let \(C\) be a communicating class. Suppose first that \(p_{ij}=0\) for every \(i\in C\) and \(j\notin C\). For each \(i\in C\), all transition probability is then assigned to states in \(C\), so \(\sum_{j\in C}p_{ij}=\sum_{j\in S}p_{ij}=1\). Thus a one-step transition from any state in \(C\) stays in \(C\) with probability \(1\), and \(C\) is closed. Conversely, suppose that \(C\) is closed. By definition, for each \(i\in C\), \(\sum_{j\in C}p_{ij}=1\). The full row also sums to \(1\), and all entries are nonnegative, so \(\sum_{j\notin C}p_{ij}=0\). A sum of nonnegative numbers is zero only when each summand is zero. Therefore \(p_{ij}=0\) for every \(j\notin C\), as required. This proves both directions. \(\square\)
There is also a useful finite-state consequence: at least one closed communicating class exists. To see why, consider the finite collection of communicating classes and draw an arrow from one class to another when a positive transition leaves the first for a state in the second. A directed cycle among distinct classes would make the classes mutually accessible, contradicting that they are distinct communication classes. Hence this finite graph has no directed cycles. Starting at any class and following an outgoing arrow whenever one exists must therefore eventually stop; otherwise some class would repeat, producing a cycle. The class where the process stops has no outgoing arrow and is closed by the theorem.
Worked Matrix Classifications
Worked Example: One Transient Class and One Closed Class
Consider \(S=\{1,2,3,4\}\) and the transition matrix below. Identify all communication classes and determine which are closed.
Check the rows before classifying: row \(1\) sums to \(0+\tfrac12+\tfrac12+0=1\); row \(2\) sums to \(\tfrac13+\tfrac23+0+0=1\); row \(3\) sums to \(0+0+\tfrac12+\tfrac12=1\); row \(4\) sums to \(0+0+\tfrac14+\tfrac34=1\).
The positive edges among states \(1\) and \(2\) include \(1\to2\) and \(2\to1\), so these states communicate. State \(1\) also has an edge to \(3\), but neither state \(3\) nor state \(4\) has an edge leading back to \(1\) or \(2\). Thus \(\{1,2\}\) is one communication class. States \(3\) and \(4\) have edges in both directions, so they communicate with each other; they cannot communicate with \(1\) or \(2\). The classes are \(\{1,2\}\) and \(\{3,4\}\).
For \(\{1,2\}\), the entry \(p_{13}=\tfrac12>0\) is an outgoing transition, so this class is not closed. For \(\{3,4\}\), rows \(3\) and \(4\) have zero entries in columns \(1\) and \(2\), and their probabilities within \(\{3,4\}\) sum to \(\tfrac12+\tfrac12=1\) and \(\tfrac14+\tfrac34=1\), respectively. Therefore \(\{3,4\}\) is closed and is the only closed class.
Check: The within-class row sums for \(\{3,4\}\) are \(p_{33}+p_{34}=\tfrac12+\tfrac12=1\) and \(p_{43}+p_{44}=\tfrac14+\tfrac34=1\). The positive entry \(p_{13}=\tfrac12\) verifies that \(\{1,2\}\) fails the closure test.
Worked Example: Two Closed Singleton Classes
Now let \(S=\{1,2,3,4,5\}\) and consider
The row sums are, in order, \(0+\tfrac12+\tfrac12+0+0=1\), \(\tfrac12+0+0+\tfrac12+0=1\), \(0+0+1+0+0=1\), \(0+0+0+0+1=1\), and \(0+0+0+0+1=1\).
States \(1\) and \(2\) communicate because \(p_{12}=\tfrac12>0\) and \(p_{21}=\tfrac12>0\). Neither can communicate with a state that reaches back to them from \(3\), \(4\), or \(5\); those states either stay at \(3\) or move from \(4\) to \(5\). Thus \(\{1,2\}\) is a class. States \(3\), \(4\), and \(5\) each form singleton classes: \(3\) stays at \(3\), \(4\) moves to \(5\) but \(5\) cannot return to \(4\), and \(5\) stays at \(5\).
The class \(\{1,2\}\) is not closed, since \(p_{13}=\tfrac12>0\) and \(p_{24}=\tfrac12>0\). The singleton \(\{3\}\) is closed because \(p_{33}=1\) and its row has zero entries outside column \(3\). The singleton \(\{4\}\) is not closed because \(p_{45}=1>0\). The singleton \(\{5\}\) is closed because \(p_{55}=1\) and its row has zero entries outside column \(5\). The closed communicating classes are therefore \(\{3\}\) and \(\{5\}\).
Check: For \(\{3\}\), the probability of staying in the class is \(p_{33}=1\); for \(\{5\}\), it is \(p_{55}=1\). For \(\{4\}\), the probability of staying in the class is \(p_{44}=0\), while the outgoing probability is \(p_{45}=1\).
Worked Example: A Chain of Classes with Two Outgoing Edges
Use the positive transitions in the following matrix to find the classes, then test each one for closure.
Each row sums to \(1\): the five sums are \(0+1+0+0+0=1\), \(\tfrac12+0+\tfrac12+0+0=1\), \(0+0+0+1+0=1\), \(0+0+\tfrac13+0+\tfrac23=1\), and \(0+0+0+0+1=1\).
There is a path \(1\to2\), and the positive transition \(2\to1\) has probability \(\tfrac12\), so \(1\) and \(2\) communicate. The transition \(2\to3\), with probability \(\tfrac12\), leaves this class; no state among \(3,4,5\) has a path back to \(1\) or \(2\). Thus \(\{1,2\}\) is a class but is not closed.
There are transitions \(3\to4\) and \(4\to3\), with probabilities \(1\) and \(\tfrac13\), so \(\{3,4\}\) is another communication class. The positive entry \(p_{45}=\tfrac23\) leaves that class, so it is not closed. State \(5\) is a singleton class and is closed because \(p_{55}=1\) and there is no positive entry from row \(5\) to another state. Hence \(\{5\}\) is the only closed class.
Check: The outgoing probabilities from \(\{1,2\}\) include \(p_{23}=\tfrac12\), and those from \(\{3,4\}\) include \(p_{45}=\tfrac23\). For \(\{5\}\), the within-class row sum is \(p_{55}=1\). These entries give the closure decisions directly.
What the Closure Test Does—and Does Not—Say
A closed class is a set from which the chain cannot leave in one step, and therefore cannot leave in any later step. Indeed, if every transition from a state in \(C\) stays in \(C\) with probability \(1\), then after each step the chain remains in \(C\) with probability \(1\); induction gives the same statement at every finite time. This does not mean that every state in \(C\) is fixed: the chain may move among several states within the class.
By contrast, a communicating class that has an outgoing edge is not closed, even if it can reach a closed class. In the third example, \(\{1,2\}\) can reach \(\{3,4\}\), which can reach \(\{5\}\), but this does not make either earlier class closed. Closure asks whether a positive transition can leave the class, not whether the class can eventually reach a destination from which there is no return.
Common mistake. In the second example, a mistaken reading might treat the zero entry \(p_{41}=0\) as an edge and claim that state \(4\) can return to state \(1\). Since \(1\) can reach \(4\) along \(1\to2\to4\), that false edge would incorrectly merge states \(1,2,4\) into one communication class. The correction is to include an edge only when its matrix entry is strictly positive: \(p_{41}=0\) gives no transition, and the actual edge from \(4\) goes to \(5\). Thus \(\{1,2\}\), \(\{4\}\), and \(\{5\}\) remain distinct classes.
For a final check, inspect each class row by row rather than relying on its visual position in the matrix. A block of positive entries within a set does not establish that it is closed; all entries in that set's rows and in columns outside the set must be zero. Conversely, if those outside entries are all zero, the row-stochastic condition guarantees that the full probability mass remains in the class.
Check Your Understanding
For each question, use strictly positive matrix entries as edges, and include a transition in the closure test only when its probability is positive.
- In the first worked example, which positive entry proves that \(\{1,2\}\) is not closed?
- In the second worked example, why is \(\{4\}\) a communicating class but not a closed class?
- Suppose a communicating class \(C\) has \(p_{ij}=0\) for every \(i\in C\) and \(j\notin C\). Use the row-sum condition to show that every state in \(C\) transitions into \(C\) with probability \(1\).
- Can a closed class contain multiple states? Identify one in the worked examples and give the positive transitions showing its states communicate.
- Why does a zero matrix entry not give a directed edge, even if the row and column labels otherwise suggest a possible move?