From Transition Probabilities to a Directed Graph
A transition matrix records probabilities, while state classification depends on which transitions are possible and how those transitions can be combined into paths. The useful first step is therefore to discard the sizes of positive probabilities, but not their distinction from zero: a positive entry gives an edge, and a zero entry does not. Once the directed graph is identified, its paths reveal which states can reach one another, which states form communicating classes, and whether a class is closed.
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})\). Its transition matrix is \(P=(p_{ij})\), where \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\). Each row is a probability distribution, so its entries are nonnegative and sum to \(1\). For \(n\ge1\), write \(p_{ij}^{(n)}\) for the \((i,j)\) entry of \(P^n\), the probability of going from \(i\) to \(j\) in \(n\) steps.
For a state \(i\), its positive return lengths are the integers \(n\ge1\) for which \(p_{ii}^{(n)}>0\). If this set is nonempty, the period of \(i\) is the greatest common divisor of its positive return lengths. If the set is empty, the state has no period under this definition: the gcd of an empty set of positive integers is not defined. In the finite matrix calculations below, exact zeros and positive fractions make the edge decisions unambiguous.
Proof. For \(n=1\), the claim is exactly the edge definition. For general \(n\), repeated matrix multiplication gives \(p_{ij}^{(n)}=\sum_{i_1,\ldots,i_{n-1}\in S}p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}j}\). Every term is nonnegative. A term is positive exactly when every factor in its product is positive, which is exactly a path from \(i\) to \(j\) with the indicated intermediate states. A finite sum of nonnegative terms is positive exactly when at least one term is positive. Thus the matrix entry is positive exactly when at least one such path exists. Accessibility is therefore graph reachability. It is reflexive because of length-zero paths, symmetric by the definition of communication, and transitive because paths can be concatenated; hence communication partitions the states into equivalence classes. \(\square\)
This result explains why exact entries matter: a small positive probability still creates an edge, whereas an entry equal to zero cannot be treated as a possible move. It also gives a direct test for closure: a communicating class is closed exactly when none of its vertices has an edge leading outside the class. If an edge leaves, its endpoint is accessible from the class but cannot communicate back into it; if there is no outward edge, no path can leave, since any path leaving would have a first edge that leaves.
A Matrix-Based Classification Procedure
Confirm that all entries are nonnegative and every row sums to \(1\). Keep the state labels in a fixed order.
For each row \(i\), draw \(i\to j\) for every entry \(p_{ij}>0\), including a self-loop when \(p_{ii}>0\).
Follow directed paths from each state. Group states together only when every state in the group can reach every other state.
A class is closed when no positive entry in any of its rows leads outside it. The chain is irreducible exactly when there is one communicating class containing all states.
For each state, identify positive return lengths and take their gcd. If there is no positive return length, report that its period is undefined.
The examples apply this procedure to finite matrices. In each case the row sums are checked before the positive entries are interpreted as transition probabilities. For periods, a claim about all return lengths requires a path-based argument, not just a few computed powers.
Worked Example: Two Closed Classes with Period Two
Classify the states of the chain with \(S=\{1,2,3,4\}\) and
The row sums are \(0+1+0+0=1\), \(\tfrac12+0+\tfrac12+0=1\), \(0+0+0+1=1\), and \(0+0+1+0=1\). Thus each row is a probability distribution. The edges are \(1\to2\), \(2\to1\), \(2\to3\), \(3\to4\), and \(4\to3\).
States \(1\) and \(2\) communicate because each has an edge to the other. Neither reaches \(3\) or \(4\) and then returns, so their class is \(\{1,2\}\). States \(3\) and \(4\) communicate by their opposing edges, and no edge leaves that pair, so their class \(\{3,4\}\) is also closed. The edge \(2\to3\) leaves \(\{1,2\}\), making that class nonclosed. Since there are two classes, the chain is not irreducible.
Every return to state \(1\) must alternate \(1\to2\to1\to2\to1\), so every positive return length is even. Length \(2\) is possible, with probability \(p_{12}p_{21}=1\cdot\tfrac12=\tfrac12>0\). Therefore the return lengths for state \(1\) include \(2\), and all are multiples of \(2\), giving period \(2\). A return to state \(2\) must also use the alternating edges: taking \(2\to3\) prevents a return. Its length-\(2\) return has probability \(p_{21}p_{12}=\tfrac12\cdot1=\tfrac12>0\), so state \(2\) also has period \(2\).
For states \(3\) and \(4\), every return alternates between them, and a return of length \(2\) is possible with probability \(p_{34}p_{43}=1\cdot1=1\). All return lengths are even, so both states have period \(2\). Thus each communicating class has period \(2\), determined here directly by its alternating paths.
Worked Example: Reachable States, but Several Classes
Consider \(S=\{1,2,3,4,5\}\) and
The row sums are \(0+\tfrac12+\tfrac12+0+0=1\), \(\tfrac12+0+0+\tfrac12+0=1\), \(0+0+\tfrac12+0+\tfrac12=1\), \(0+0+0+1+0=1\), and \(0+0+0+0+1=1\). The edges are \(1\to2\), \(1\to3\), \(2\to1\), \(2\to4\), \(3\to3\), \(3\to5\), \(4\to4\), and \(5\to5\).
States \(1\) and \(2\) communicate through their two opposing edges. Neither state \(3\), \(4\), nor \(5\) can return to \(1\) or \(2\), so \(\{1,2\}\) is a class. State \(3\) communicates with itself and not with any other state, so \(\{3\}\) is a class. The same reasoning gives the singleton classes \(\{4\}\) and \(\{5\}\). The edges \(1\to3\) and \(2\to4\) leave \(\{1,2\}\), while \(3\to5\) leaves \(\{3\}\); these classes are not closed. No edge leaves \(\{4\}\) or \(\{5\}\), so both are closed. There is more than one class, hence the chain is not irreducible.
For state \(1\), any path that returns to \(1\) must take \(1\to2\to1\): moving from \(1\) to \(3\) leads only to \(3\) and \(5\), and moving from \(2\) to \(4\) leads only to \(4\). Thus all positive return lengths to \(1\) are even, and length \(2\) has probability \(p_{12}p_{21}=\tfrac12\cdot\tfrac12=\tfrac14>0\). The period is \(2\). The same alternating-path argument gives period \(2\) for state \(2\). States \(3\), \(4\), and \(5\) each have a self-loop, so their return length \(1\) is positive: \(p_{33}=\tfrac12>0\), \(p_{44}=1>0\), and \(p_{55}=1>0\). A set of positive integers containing \(1\) has gcd \(1\), so each of these states has period \(1\).
Notice that states \(1\) and \(2\) can reach other classes, but that does not put those states in the same communicating class. Reachability in one direction is not communication.
Worked Example: A State with No Positive Return Length
Let \(S=\{1,2,3\}\) and
The row sums are \(0+1+0=1\), \(0+0+1=1\), and \(0+0+1=1\), so the matrix is row-stochastic. Its edges are \(1\to2\), \(2\to3\), and \(3\to3\). State \(1\) reaches \(2\) and \(3\), state \(2\) reaches \(3\), and state \(3\) cannot reach either \(1\) or \(2\). Thus all three communicating classes are singletons. The class \(\{3\}\) is closed, while \(\{1\}\) and \(\{2\}\) are not. There is no single class containing the whole space, so the chain is not irreducible.
Starting from \(1\), the chain moves to \(2\), then to \(3\), after which it stays at \(3\). It cannot return to \(1\). Hence \(p_{11}^{(n)}=0\) for every \(n\ge1\), the positive return-length set is empty, and state \(1\) has no period under the definition above. The same reasoning shows that state \(2\) has no positive return length: it moves to \(3\) and cannot return. State \(3\), in contrast, has \(p_{33}^{(1)}=1\), so its period is \(1\).
Check by paths: the only outgoing edge from \(1\) is to \(2\), and there is no path from \(2\) back to \(1\); the only outgoing edge from \(2\) is to \(3\), and there is no path from \(3\) back to \(2\). These path facts agree with the absence of positive return lengths for the first two states.
Why the Classification Works—and a Common Mistake
The matrix-to-graph conversion preserves exactly the information needed for this task: whether a transition has positive probability. The proposition proves that a positive entry of \(P^n\) corresponds exactly to a path of length \(n\); consequently, there is no need to approximate matrix powers numerically to decide whether a path exists. For exact matrices, graph inspection also avoids rounding errors that could turn a small positive entry into zero, or a zero into a spurious edge.
A common mistake is to assign a period to every state without checking whether it can return. In the last example, an incorrect calculation might write \(d(1)=\gcd\{n\ge1:p_{11}^{(n)}>0\}=1\), treating the absent return lengths as if they implied period \(1\). But \(p_{11}^{(n)}=0\) for every positive \(n\), so the set whose gcd is requested is empty. Its gcd is not defined; the correct report is that state \(1\) has no period under this definition. Always check that at least one positive return length exists before taking a gcd.
Another error is to call every state reachable from a state part of its communicating class. In the second example, \(1\) reaches \(3\), but \(3\) cannot reach \(1\); the states therefore belong to different classes. A reliable classification keeps the tests separate: first find one-way reachability, then group states only when reachability holds in both directions, and finally test whether any edge leaves each group.
| Question | Exact matrix or graph test |
|---|---|
| Is \(j\) accessible from \(i\)? | There is a directed path from \(i\) to \(j\). |
| Do \(i\) and \(j\) communicate? | There are directed paths in both directions. |
| Is a communicating class closed? | No positive matrix entry in its rows leads outside it. |
| Is the chain irreducible? | All states belong to one communicating class. |
| Does state \(i\) have a period? | At least one \(p_{ii}^{(n)}>0\) for \(n\ge1\); then take the gcd of the positive return lengths. |
Check Your Understanding
For each question, distinguish a positive-probability edge from a path that may require several steps.
- In a transition matrix, what graph feature corresponds to an entry \(p_{ij}=0\), and what feature corresponds to \(p_{ij}>0\)?
- Can two states communicate if one is accessible from the other but the reverse path does not exist? Explain.
- What matrix-row check should be completed before interpreting positive entries as transition probabilities?
- In the first worked example, why does the edge \(2\to3\) make \(\{1,2\}\) nonclosed without joining states \(3\) and \(4\) to its communicating class?
- What should be reported as the period of a state for which \(p_{ii}^{(n)}=0\) for every \(n\ge1\), and why?