Strongly Connected Components in Transition Graphs

From Transition Probabilities to a Directed Graph

A transition matrix records probabilities, while a directed graph records which one-step moves are possible. The graph can make the organization of a chain easier to see: a path represents a sequence of possible moves, and a strongly connected component groups states that can all reach one another. The key is to distinguish a one-way path from mutual reachability. A single edge from one group of states to another does not, by itself, make those states part of the same communicating class.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite 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\). Its transition graph has vertex set \(S\), and has a directed edge \(i\to j\) exactly when \(p_{ij}>0\). A directed path of length \(n\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_n=j\) for which every edge \(i_{r-1}\to i_r\) is present. We allow a path of length zero from a state to itself.

The graph definition and the Markov-chain definition agree because a finite path is possible exactly when its probability is positive. In particular, the length of the path need not be fixed in advance: accessibility means that some finite number of steps suffices. This is a graph question about possible transitions, not a statement that the chain is stationary or that it will follow a particular path with certainty.

Proof. We prove the first statement by induction on \(n\). For \(n=0\), \(P^0\) is the identity matrix: \(p_{ij}^{(0)}>0\) exactly when \(i=j\), which is exactly when there is a length-zero path. Suppose the statement holds for \(n\). By matrix multiplication and the Chapman–Kolmogorov equations, \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). All terms are nonnegative, so this sum is positive exactly when at least one term is positive. By the induction hypothesis, that happens exactly when for some \(k\) there is a length-\(n\) path from \(i\) to \(k\), followed by an edge \(k\to j\). Such a concatenation is a length-\((n+1)\) path, and every length-\((n+1)\) path has that form by taking \(k\) to be its next-to-last vertex. This proves the first statement for every \(n\). Accessibility is the existence of a path of some finite length, equivalently a positive \(n\)-step probability for some \(n\). Thus mutual accessibility is precisely strong connectivity, and maximal mutually accessible sets are exactly the strongly connected components. \(\square\)

A Reachability Procedure

For a finite graph, strong components can be found by computing which vertices are reachable from which others. The following Boolean procedure is useful when the graph is given as a matrix. A Boolean entry is either \(0\) or \(1\); in this calculation, “or” and “and” replace ordinary addition and multiplication.

To justify the update, order the states as \(1,\ldots,m\). Before processing \(k\), interpret \(R_{ij}\) as recording whether there is a path from \(i\) to \(j\) whose intermediate vertices are among \(1,\ldots,k-1\). A path that uses \(k\) can be split at \(k\) into a path from \(i\) to \(k\) and one from \(k\) to \(j\); each part needs no intermediate vertex outside \(1,\ldots,k-1\). Conversely, concatenating those two paths gives a path from \(i\) to \(j\). Repeated vertices do not cause a problem: if a path exists, removing the segment between two repeated occurrences of a vertex gives a shorter path with the same endpoints, and repeating this removal yields a path with no repeated vertices (or the length-zero path when the endpoints coincide). Thus every reachable pair has a path whose intermediate vertices are among the states considered by the procedure. After all \(m\) updates, \(R_{ij}=1\) exactly for reachable pairs.

The grouping rule produces a partition. Each state is related to itself. If \(i\) is mutually reachable with \(j\), then \(j\) is mutually reachable with \(i\). If \(i\) is mutually reachable with \(j\), and \(j\) with \(k\), concatenating paths gives paths in both directions between \(i\) and \(k\). So mutual reachability is reflexive, symmetric, and transitive; its equivalence classes are disjoint and cover \(S\). This is the same partition as the communicating classes.

Worked Examples

Why Components Cannot Form a Directed Cycle

It can be helpful to compress each strongly connected component into a single vertex and retain the directed edges between different components. The resulting graph records which components can be reached from which others. It cannot contain a directed cycle through distinct components.

Proof. Suppose there is a directed cycle of components \(C_1,C_2,\ldots,C_r,C_1\), where the listed components are distinct. An edge from \(C_a\) to \(C_{a+1}\) means that some vertex of \(C_a\) has an edge to some vertex of \(C_{a+1}\). Since vertices within each component can reach one another, any vertex in \(C_1\) can reach the start of the first cross-component edge, then follow the cycle, and then reach any chosen vertex in \(C_1\). More importantly, following part of the cycle gives paths from vertices in \(C_1\) to vertices in each \(C_a\), and following the remaining part gives paths back. Hence vertices in \(C_1\) and \(C_a\) are mutually reachable for every \(a\). They must belong to the same maximal strongly connected set, contradicting that the components are distinct. Therefore no such directed cycle exists. \(\square\)

This proposition explains why a diagram of components can have one-way arrows but cannot have a loop of arrows that returns to its starting component. If such a return route existed, the states along that route would be mutually reachable and should have been grouped together in the first place.

A Common Mistake

A frequent error is to merge two states as soon as there is an edge from one to the other. In the first worked example, the edge \(2\to3\) is real, but it does not show that \(2\) and \(3\) communicate. The incorrect calculation is: “\(2\to3\), so \(2\leftrightarrow3\), and \(\{1,2,3,4\}\) is one component.” This uses only one direction. The correction is to check both reachability statements: \(2\) reaches \(3\), but \(3\) cannot reach \(2\). Therefore \(2\not\leftrightarrow3\), and the two components remain \(\{1,2\}\) and \(\{3,4\}\).

For a small graph, tracing paths by eye is often enough. For a larger finite graph, the reachability procedure is systematic: initialize from positive entries and the diagonal, update through intermediate vertices, and group states only when reachability holds in both directions. In every case, the one-step probabilities determine the edges, while mutual reachability—not the mere presence of an edge—determines the communicating classes.