From Return Times to Directed Cycles
A period is defined through the possible return times to a state. In a finite transition graph, those return times are walks that begin and end at the same vertex. Directed cycles provide a more compact way to study them: every closed walk can be broken into cycles, and strong connectivity lets us connect a cycle elsewhere in the graph to a chosen state. When two cycles share a vertex or a path, their lengths can be compared directly in the gcd calculation.
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 transition graph has an edge \(i\to j\) exactly when \(p_{ij}>0\). A directed walk of length \(n\) is a sequence of \(n\) edges in the indicated direction. A directed cycle of length \(n\ge1\) is a closed walk whose vertices, other than the repeated first and last vertex, are distinct; a self-loop is a cycle of length \(1\). The graph is strongly connected if every vertex can be reached from every other vertex by a directed walk.
The graph records which transitions are possible, not their particular positive probabilities. A length-\(n\) walk from \(i\) to \(j\) has positive probability: the probability of following its specified edges is the product of \(n\) positive transition probabilities. Conversely, if \(p_{ij}^{(n)}>0\), the sum of the probabilities of the finitely many length-\(n\) walks from \(i\) to \(j\) is positive, so at least one such walk exists. Thus return-time lengths are exactly the lengths of positive-probability closed walks at the state.
For a finite graph, there are only finitely many simple directed cycles, although their number can be large. The following result explains why their lengths give the period. It uses strong connectivity to connect a cycle to the state under study, even when that cycle does not pass through that state.
Proof. Write \(c=\gcd\{\ell(\gamma):\gamma\in C\}\). First, every positive-length closed walk can be decomposed into simple directed cycles, with the sum of their lengths equal to the length of the walk. To verify this, consider a closed walk of length \(n\). If it is already a simple cycle, there is nothing to decompose. Otherwise, some vertex is repeated before the final return to the starting vertex. Choose a repeated-vertex segment with no repeated internal vertices; this segment is a simple cycle. Removing that segment leaves a closed walk, possibly of length zero, whose length is reduced by the length of the removed cycle. Repeating this operation terminates because the length decreases at every removal. Consequently, \(c\) divides the length of every positive-length closed walk at \(i\), so \(c\) divides every element of \(R_i\). Hence \(c\mid d(i)\).
For the reverse divisibility, take any simple cycle \(\gamma\), of length \(L\), based at a vertex \(u\). If \(u=i\), then \(L\in R_i\), so \(d(i)\mid L\). If \(u\ne i\), strong connectivity supplies a directed path from \(i\) to \(u\) of length \(a\ge1\) and a directed path from \(u\) to \(i\) of length \(b\ge1\). Following those paths gives a return walk at \(i\) of length \(a+b\); inserting \(\gamma\) between them gives one of length \(a+L+b\). Both lengths are in \(R_i\). Therefore \(d(i)\) divides both, and so divides their difference \(L\). This holds for every simple cycle, giving \(d(i)\mid c\). The two divisibilities imply \(d(i)=c\). \(\square\)
Using Shared Paths
The theorem gives a practical way to organize a calculation. Identify the simple directed cycles and their lengths, then take their gcd. A pair of cycles that share a vertex can both be started at that vertex: each length is then itself a return time there. If they share a directed path, they share its vertices as well, so this direct comparison is available. The shared path can also make the cycles easier to find: follow the common edges until the routes separate, then track each route back to the shared part.
Do not replace “all simple cycles” by an arbitrary selection of cycles unless you have a reason that the omitted lengths cannot change the gcd. A useful partial calculation gives a multiple of the final gcd, not necessarily the final answer. The examples show how to enumerate the cycles in small graphs and verify the resulting period.
Worked Example: Two Cycles Sharing a Directed Path
Consider the state space \(S=\{0,1,2,3\}\) and the transition matrix, in that state order, $$ P=\begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ \tfrac12&0&0&\tfrac12\\ 1&0&0&0 \end{bmatrix}. $$ The row sums are \(0+1+0+0=1\), \(0+0+1+0=1\), \(\tfrac12+0+0+\tfrac12=1\), and \(1+0+0+0=1\). Thus every row is a probability distribution.
The graph is strongly connected: from \(0\) one can reach \(1\), then \(2\), and then either return to \(0\) or go through \(3\) and return to \(0\). These routes also give paths from every state to \(0\), so every state can reach every other state by going through \(0\). The only simple cycles are \(0\to1\to2\to0\), of length \(3\), and \(0\to1\to2\to3\to0\), of length \(4\). They share the directed path \(0\to1\to2\).
Taking the gcd of the cycle lengths gives \(\gcd(3,4)=1\), so the theorem gives \(d(0)=1\). Directly, the two cycles have probabilities \(\tfrac12\) and \(\tfrac12\) when followed from \(0\), so \(3,4\in R_0\). Any common divisor of all return times must divide both \(3\) and \(4\), hence must be \(1\); the cycle-length characterization confirms that no other cycle imposes a different gcd.
Worked Example: Shared Cycles with an Even Gcd
On \(S=\{0,1,2,3\}\), use $$ P=\begin{bmatrix} 0&1&0&0\\ \tfrac12&0&\tfrac12&0\\ 0&0&0&1\\ 1&0&0&0 \end{bmatrix}. $$ The row sums are \(0+1+0+0=1\), \(\tfrac12+0+\tfrac12+0=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\). Every row sums to \(1\).
The graph is strongly connected: the route \(0\to1\to2\to3\to0\) visits all states and returns to its start, so from any state one can continue around the route to reach any other. The simple cycles are \(0\to1\to0\), of length \(2\), and \(0\to1\to2\to3\to0\), of length \(4\). They share the edge \(0\to1\). Their gcd is \(\gcd(2,4)=2\), and therefore \(d(0)=2\).
For a direct check, the length-\(2\) return walk at \(0\) has probability \(1\cdot\tfrac12=\tfrac12>0\), and the length-\(4\) return walk has probability \(1\cdot\tfrac12\cdot1\cdot1=\tfrac12>0\). Thus any divisor of every return time divides \(2\) and \(4\), so it divides \(2\). The cycle characterization says every return time is divisible by the gcd of the simple cycle lengths, which is \(2\). Together these checks give period exactly \(2\).
Worked Example: Cycles Meeting at a Vertex Away from the Chosen State
Consider \(S=\{0,1,2,3\}\) with $$ P=\begin{bmatrix} 0&1&0&0\\ \tfrac12&0&\tfrac12&0\\ 0&0&0&1\\ 0&1&0&0 \end{bmatrix}. $$ The row sums are \(0+1+0+0=1\), \(\tfrac12+0+\tfrac12+0=1\), \(0+0+0+1=1\), and \(0+1+0+0=1\). Every row sums to \(1\).
The graph is strongly connected: \(0\to1\to2\to3\to1\) reaches the states \(1,2,3\) from \(0\), and the edge \(1\to0\) returns to \(0\). From \(2\) or \(3\), the route reaches \(1\), from which one can reach \(0\) or continue around the cycle through \(2\) and \(3\). The simple cycles are \(0\to1\to0\), of length \(2\), and \(1\to2\to3\to1\), of length \(3\). They meet at vertex \(1\), but the second cycle does not pass through \(0\).
The gcd of all simple cycle lengths is \(\gcd(2,3)=1\); the theorem therefore gives \(d(0)=1\). To see how the connecting paths work for the cycle not based at \(0\), take the path \(0\to1\) of length \(1\) and the path \(1\to0\) of length \(1\). Without inserting the length-\(3\) cycle they form a return walk at \(0\) of length \(1+1=2\). Inserting that cycle gives a return walk of length \(1+3+1=5\). Both are possible: their probabilities are \(\tfrac12\) and \(\tfrac12\cdot1\cdot1\cdot\tfrac12=\tfrac14\), respectively. Since \(\gcd(2,5)=1\), these return times already force the period at \(0\) to be \(1\), in agreement with the theorem.
What the Gcd Calculation Does—and Does Not—Use
In each example, the positive probabilities establish which edges exist. Once the transition graph is fixed, the gcd calculation uses the lengths of its cycles, not the sizes of the positive probabilities. Changing a positive edge probability while keeping it positive leaves the graph and its cycle lengths unchanged. Removing that edge by setting its probability to zero can change the cycles, so the period must then be recalculated.
Common mistake. It is wrong to take the gcd of lengths of arbitrary paths from the state and call it the period. In the first example, the paths \(0\to1\) and \(0\to1\to2\) have lengths \(1\) and \(2\), whose gcd is \(1\). But neither path returns to \(0\), so neither length belongs to \(R_0\). The valid cycle lengths are \(3\) and \(4\), and these give \(d(0)=1\) for the right reason. In another graph, using non-return path lengths could produce a gcd that does not match the return-time gcd at all. Always check that each length being used corresponds to a closed walk at the state, or use the proved cycle-length characterization.
A practical calculation can therefore proceed in three stages: check that the transition graph is strongly connected; identify the simple directed cycles and their lengths; and take the gcd of those lengths. Shared vertices and paths are especially useful because they make cycle routes visible and help prevent counting an open path as a return. In larger graphs, cycle enumeration can be demanding, so any shorter list used in place of all simple cycles must be justified rather than assumed to be sufficient.
Check Your Understanding
For each question, distinguish a directed return cycle from an arbitrary path and state which graph information supports the gcd calculation.
- A strongly connected transition graph has simple-cycle lengths \(6\) and \(9\), and no other simple cycles. What period does the cycle-length characterization give?
- Two simple directed cycles share a vertex and have lengths \(5\) and \(8\). Explain why both lengths are return times at their shared vertex and find their gcd.
- Why does a length-\(n\) walk with positive-probability edges correspond to \(p_{ij}^{(n)}>0\) for its endpoints?
- In the third worked example, identify the two paths connecting state \(0\) and state \(1\), and compute the return-walk lengths obtained with and without inserting the length-\(3\) cycle.
- A calculation lists two cycle lengths but does not establish that other simple cycles are absent. What can and cannot be concluded from the gcd of the listed lengths alone?