State Classification Workshop: Directed Graphs

From Transition Probabilities to a Directed Graph

A finite Markov chain can be studied through the routes its transitions permit, without carrying every probability through each calculation. The graph records exactly which one-step moves have positive probability. Directed paths then encode accessibility, and groups of vertices that can all reach one another encode communication classes. The graph also records return-path lengths, which determine periods.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain with finite state space \(S\) and transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\in S\). Draw 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\) such that each consecutive pair is an edge. A path of length zero from a state to itself is allowed.

Accessibility concerns a possible route in the directed graph, not how likely that route is relative to other routes. A path with positive-probability edges has positive probability of being followed in its specified number of steps. This gives the basic connection between the graph and the chain.

Proof. For \(n=0\), the transition matrix \(P^{(0)}\) is the identity matrix: \(p_{ij}^{(0)}\) is positive exactly when \(i=j\), which is exactly when there is a length-zero path from \(i\) to \(j\). Now suppose the claim holds for \(n\). By Chapman–Kolmogorov, \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). Every term is nonnegative, so this sum is positive exactly when at least one \(k\in S\) has both \(p_{ik}^{(n)}>0\) and \(p_{kj}>0\). By the induction hypothesis, the first condition means there is a length-\(n\) path from \(i\) to \(k\); the second means there is an edge from \(k\) to \(j\). Together they give a length-\((n+1)\) path. Conversely, the last edge of any length-\((n+1)\) path comes from some \(k\), and its first \(n\) edges give \(p_{ik}^{(n)}>0\); hence the corresponding term in the sum is positive. Induction proves the claim for all \(n\). Allowing any \(n\ge0\) gives the accessibility statement. \(\square\)

Communication Classes and Closed Classes

In graph language, a communication class is a strongly connected component: within it, every vertex can reach every other vertex by a directed path. These components partition the state space. To see why, communication is reflexive because of length-zero paths, symmetric by definition, and transitive because directed paths can be concatenated. Thus it is an equivalence relation, and its equivalence classes are exactly the communication classes.

Being a communication class does not imply being closed. A component is closed only if none of its vertices has an edge leaving the component. In a finite chain, the graph of communication classes has no directed cycles between distinct classes: a cycle among classes would make their states mutually accessible, so they would belong to the same class. In particular, at least one communication class is closed. Indeed, starting from any class and following edges to new classes cannot continue indefinitely without repeating a class; a repetition would create a cycle. Since there are finitely many classes, the process must reach one with no outgoing edge to a different class.

Periods from Return Paths

A return path at \(i\) is a directed path of positive length from \(i\) back to \(i\). Its length belongs to the return-time set \(\{n\ge1:p_{ii}^{(n)}>0\}\). If that set is nonempty, the period \(d(i)\) is the greatest common divisor of its elements. If there is no positive-length return path, use the convention \(d(i)=0\). For states in the same communication class that have positive-length returns, their periods agree.

Proof. If \(i=j\), the conclusion is immediate. Otherwise choose a path from \(i\) to \(j\) of length \(a\ge1\) and a path from \(j\) to \(i\) of length \(b\ge1\). Concatenating them gives positive-length return paths at both states, so both periods are defined by nonempty sets. Let \(n\) be any positive return length at \(j\). At \(i\), there is a return path of length \(a+b\), and another of length \(a+n+b\), formed by inserting the length-\(n\) return at \(j\). Therefore \(d(i)\) divides both lengths and hence divides their difference \(n\). Since this holds for every return length at \(j\), \(d(i)\) divides \(d(j)\). Reversing the roles of \(i\) and \(j\) shows that \(d(j)\) divides \(d(i)\), so the two positive integers are equal. \(\square\)

For a self-loop \(i\to i\), there is a return of length \(1\), so \(d(i)=1\). Without a self-loop, do not infer the period from the shortest return alone: the gcd must use all possible return lengths, or enough lengths to determine their gcd. For example, return lengths \(2\) and \(3\) already force period \(1\).

A Practical Graph-Classification Procedure

For a finite chain, the following sequence keeps the questions separate. First, include an edge exactly for each positive transition probability. Second, test accessibility by searching for directed paths. Third, group states that are mutually accessible; these are the communication classes. Fourth, check each class for outgoing edges to determine whether it is closed. The chain is irreducible precisely when there is one communication class containing the whole state space. Finally, for each state with a return path, find return-path lengths and take their gcd; communicating states share the same period.

Common Pitfalls

A frequent error is to call every communication class closed. In the first example, \(\{1,2\}\) is a communication class, but the positive-probability edge \(2\to3\) leaves it, so it is not closed. The correction is to inspect every edge starting in the class; closure requires that each such edge end inside the class.

Another error is to define a state's period as its shortest return length. In the three-state irreducible example, state \(1\) has a return of length \(2\), but it also has a return of length \(3\). Their gcd is \(1\), not \(2\). Use the gcd of return lengths, not just the minimum. Finally, an absent edge means probability zero, not merely a transition that was omitted from a drawing by accident; the graph must include every positive-probability transition.

Graph classification captures which transitions are possible, but not their relative probabilities. Two chains with the same positive-edge graph have the same accessibility relations, communication classes, closed classes, irreducibility, and periods, even if their positive transition probabilities differ. Questions about hitting probabilities, expected times, or long-run frequencies require additional information and are not determined by the graph alone.