From States to Components
A transition graph can be difficult to read state by state when it contains several groups of states with frequent movement within a group and occasional movement out of it. The useful simplification is to treat each communicating class as one vertex, then draw an arrow whenever a transition leaves one class for another. This class-level graph records the possible one-way movement through the chain without confusing it with movement back and forth within a class.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with finite state space \(S\) and transition matrix \(P=(p_{ij})\). The transition graph has an edge \(i\to j\) exactly when \(p_{ij}>0\). A path from \(i\) to \(j\) is a finite sequence of such edges; a path of length zero is allowed, so every state is accessible from itself. States \(i\) and \(j\) communicate, written \(i\leftrightarrow j\), if each is accessible from the other. A communicating class is an equivalence class under this relation.
An arrow \(C\to D\) records that a transition between the classes is possible. It does not say that every state in \(C\) can jump directly to every state in \(D\), or that the chain must eventually enter \(D\). The graph is a summary of which class-to-class moves are possible. The key structural fact is that its arrows cannot form a directed cycle: a cycle would mean that the classes on it actually communicate and therefore belong to one class.
Why Class-Level Cycles Cannot Occur
Proof. Suppose, to obtain a contradiction, that distinct communicating classes \(C_0,C_1,\ldots,C_{r-1}\) form a directed cycle, with arrows \(C_0\to C_1,\ldots,C_{r-2}\to C_{r-1},C_{r-1}\to C_0\). For every arrow \(C_\ell\to C_{\ell+1}\), choose a state in \(C_\ell\) from which the transition leaves and a state in \(C_{\ell+1}\) that it enters. Within each class, any state can reach any other state in that class, by the definition of communication. We can therefore travel within \(C_0\) to the chosen source of its outgoing edge, cross to \(C_1\), travel within \(C_1\) to its outgoing edge, and continue around the cycle. This gives a path from a state of \(C_0\) to a state of \(C_1\); continuing around the cycle and using paths within classes gives a path back from \(C_1\) to \(C_0\). Thus states in \(C_0\) and \(C_1\) communicate, contradicting that they are distinct communicating classes. No directed cycle can exist. Now start from any vertex and follow an outgoing arrow whenever one is available. Because the graph is finite and has no directed cycle, no vertex can be visited twice. The process must stop at a vertex with no outgoing arrows. By the definition of the class-level graph, that vertex is a closed communicating class. Each arrow represents a positive-probability transition, so the resulting path is also a path of positive-probability transitions in the original chain. \(\square\)
The theorem is about the graph of possible transitions. It shows that every class has a route to a closed class; it does not, by itself, make a claim about the probability of following a particular route or the time taken to do so.
Worked Examples
Worked Example: A One-Way Chain of Three Classes
Consider the chain on \(S=\{1,2,3,4,5\}\) with transition matrix
Before using the matrix, check each row: the sums are \(0+\tfrac12+\tfrac12+0+0=1\), \(\tfrac12+0+\tfrac12+0+0=1\), \(0+0+0+1+0=1\), \(0+0+0+0+1=1\), and \(0+0+0+1+0=1\).
States \(1\) and \(2\) communicate because \(1\to2\) and \(2\to1\). Their transitions to state \(3\) do not provide a path back from \(3\) to either \(1\) or \(2\). Thus their class is \(C_1=\{1,2\}\). State \(3\) forms the class \(C_2=\{3\}\): it can reach \(4\), but no state reachable from \(3\) has a path back to \(3\). States \(4\) and \(5\) communicate by the transitions \(4\to5\) and \(5\to4\), so \(C_3=\{4,5\}\).
The class-level graph has arrows \(C_1\to C_2\) and \(C_2\to C_3\). There is no arrow out of \(C_3\), so \(C_3\) is closed. The other two classes are not closed: from state \(1\) there is a transition to \(3\), and from state \(3\) there is a transition to \(4\), each outside its own class. The class graph is a chain, \(C_1\to C_2\to C_3\), with no route back along either arrow.
Check: the three classes are disjoint and contain all five states: \(\{1,2\}\cup\{3\}\cup\{4,5\}=S\). The only class with no outgoing arrow is \(\{4,5\}\), matching the direct inspection of its transitions.
Worked Example: One Class with Two Closed Destinations
Consider \(S=\{1,2,3,4\}\) and
The row sums are \(0+\tfrac12+\tfrac14+\tfrac14=1\), \(\tfrac12+0+0+\tfrac12=1\), \(0+0+1+0=1\), and \(0+0+0+1=1\). States \(1\) and \(2\) communicate because \(p_{12}=\tfrac12>0\) and \(p_{21}=\tfrac12>0\). Neither state \(3\) nor state \(4\) can reach either of them. Each of \(3\) and \(4\) is an absorbing state, so the classes are \(C_1=\{1,2\}\), \(C_2=\{3\}\), and \(C_3=\{4\}\).
From \(C_1\), there is an arrow to \(C_2\) because \(p_{13}=\tfrac14>0\), and an arrow to \(C_3\) because \(p_{14}=\tfrac14>0\) (also \(p_{24}=\tfrac12>0\)). There are no arrows out of \(C_2\) or \(C_3\), so both are closed. This class graph branches: one class has possible transitions to two different closed classes.
Check: \(C_1\) is not closed because its row for state \(1\) has positive probabilities \(\tfrac14\) to each of states \(3\) and \(4\), both outside \(C_1\). Classes \(C_2\) and \(C_3\) are closed because their only transitions are \(3\to3\) and \(4\to4\).
Worked Example: Internal Loops Do Not Change the Class Graph
Take \(S=\{1,2,3,4,5\}\) and the matrix
The row sums are \(\tfrac12+\tfrac14+\tfrac14=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), \(\tfrac12+\tfrac14+\tfrac14=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(1=1\). States \(1\) and \(2\) communicate through their positive transitions in both directions, giving \(C_1=\{1,2\}\). States \(3\) and \(4\) also communicate, giving \(C_2=\{3,4\}\). State \(5\) is its own class \(C_3=\{5\}\).
The self-transitions at states \(1,2,3,4\) do not split either two-state communicating class: communication depends on paths in both directions, and the transitions between the two states in each pair remain positive. The class-level arrows are \(C_1\to C_2\), since states \(1\) and \(2\) can transition to state \(3\), and \(C_2\to C_3\), since states \(3\) and \(4\) can transition to state \(5\). There is no arrow out of \(C_3\), making it the only closed class.
Check: \(C_1\) is not closed because \(p_{13}=\tfrac14>0\), and \(C_2\) is not closed because \(p_{35}=\tfrac14>0\). The fifth row has no positive entry outside \(C_3\), so \(C_3\) is closed.
Reading the Graph Without Overstating It
To analyze a finite transition graph reliably, first group states according to communication, then draw arrows between distinct groups, and finally check which groups have any outgoing arrows. This order matters. If one looks only at individual arrows, a one-way transition can be mistaken for communication; if one checks only a single representative state in a class, an outgoing edge from another state can be missed.
Use paths of positive-probability transitions in both directions. A direct edge in one direction alone does not establish communication.
For distinct classes \(C,D\), include \(C\to D\) if at least one transition from a state in \(C\) to a state in \(D\) has positive probability.
A class is closed exactly when none of its states has a positive-probability transition to a state outside the class. Equivalently, its vertex has no outgoing arrow.
The class-level graph has no directed cycle. If a proposed cycle appears, at least two of the supposed classes must actually communicate and should be grouped together.
Common mistake: treating a one-way edge as communication. In the first example, \(p_{23}=\tfrac12>0\), so there is an edge \(2\to3\). It would be wrong to combine states \(2\) and \(3\) into one communicating class on this basis. From state \(3\), the only next state is \(4\); from \(4\), the only next state is \(5\); and from \(5\), the only next state is \(4\). None of these paths returns to \(2\). Therefore \(2\) and \(3\) do not communicate, and the correct class-level arrow is \(\{1,2\}\to\{3\}\), not a single class containing both.
A second useful check is to test closedness across the whole class, not just one state. For a class \(C\), the condition is that \(p_{ij}=0\) for every \(i\in C\) and every \(j\notin C\). One positive transition to the outside is enough to show that \(C\) is not closed. Conversely, declaring a class closed requires checking that no such transition exists from any of its states.
Check Your Understanding
Use paths of positive-probability transitions, and distinguish carefully between an edge between states and an arrow between classes.
- In the first worked example, why do states \(1\) and \(2\) communicate, but state \(3\) does not belong to their class?
- In the second example, list every arrow in the class-level graph and identify all its closed classes.
- Suppose a class has an outgoing arrow to a second class, and that second class has an arrow back to the first. What does this imply about the two proposed classes?
- Why can a finite class-level graph with no directed cycles not have a path that continues indefinitely while following outgoing arrows?
- What must be checked in a transition matrix before using its positive entries to form a transition graph?