From Return Times to a Greatest Common Divisor
In a discrete-time Markov chain, a state may be revisited after several different numbers of steps. The period records the common arithmetic spacing among all possible return times. Computing it is a greatest-common-divisor problem, but there is an important practical caution: finding several return times and taking their gcd gives a candidate, not necessarily the final period. A later return time can reduce that gcd.
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(\sum_{j\in S}p_{ij}=1\) for every \(i\). The time-\(n\) information is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Write \(p_{ij}^{(n)}=(P^n)_{ij}\). For a state \(i\), consider positive integers \(n\) for which \(p_{ii}^{(n)}>0\): these are precisely the step lengths at which returning to \(i\) has positive probability.
For a finite list \(n_1,\ldots,n_r\) of observed return times, \(\gcd(n_1,\ldots,n_r)\) is always a multiple of \(d(i)\): the period divides every return time, and therefore divides their gcd. The reverse need not hold. The finite-list gcd can be strictly larger until enough return times have been found.
Why a Finite List Can Determine an Infinite GCD
The return-time set may contain infinitely many integers. Nevertheless, if it is nonempty, some finite subset already has gcd equal to the period. This fact explains why a finite certificate exists, although it does not by itself say how many return lengths must be checked in a particular chain.
Proof. List the elements of \(R_i\) in increasing order, either as a finite list or as an infinite sequence \(r_1,r_2,\ldots\). In the finite case, taking the entire list proves the claim. In the infinite case, define \(g_k=\gcd(r_1,\ldots,r_k)\). Each \(g_{k+1}\) divides \(g_k\), because adding another integer to the list can only restrict the common divisors. Whenever \(g_{k+1}\ne g_k\), it is a strictly smaller positive integer than \(g_k\). A sequence of positive integers cannot strictly decrease infinitely many times, so there is an index \(K\) after which \(g_k=g_K\) for every \(k\ge K\). If some \(r_j\) with \(j>K\) were not divisible by \(g_K\), then \(\gcd(r_1,\ldots,r_j)\) would differ from \(g_K\), contradicting this stabilization. Thus \(g_K\) divides every element of \(R_i\). Conversely, \(d(i)\) divides each of \(r_1,\ldots,r_K\), so \(d(i)\) divides \(g_K\). Since \(g_K\) is a common divisor of all of \(R_i\), it cannot exceed the greatest common divisor \(d(i)\); and since \(d(i)\) divides \(g_K\), it cannot be smaller. Hence \(g_K=d(i)\), as required. \(\square\)
There is also a useful structural check on return lengths. The Chapman–Kolmogorov equation says that \(P^{m+n}=P^mP^n\). In particular, two return lengths can be concatenated to give another return length.
Proof. By matrix multiplication and nonnegativity of transition probabilities, \(\displaystyle p_{ii}^{(m+n)}=\sum_{j\in S}p_{ij}^{(m)}p_{ji}^{(n)}\ge p_{ii}^{(m)}p_{ii}^{(n)}>0\). The inequality uses the \(j=i\) term of the sum, and the final strict inequality follows from \(m,n\in R_i\). Thus \(m+n\in R_i\). \(\square\)
This proposition can help explain additional returns, but it does not license stopping after a few lengths. A practical calculation can use exact powers of \(P\), or trace paths whose transitions all have positive probability. When a finite set of return lengths has gcd \(g\), the period must divide \(g\); a finite certificate of equality requires knowing that the gcd of the full set cannot be reduced by additional return lengths.
Worked Calculations
Worked Example: A Deterministic Four-Step Return
Consider the chain on \(S=\{0,1,2,3\}\) with transition matrix
Each row sums to \(1\): the four row sums are \(0+1+0+0=1\), \(0+0+1+0=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\). Starting at state \(0\), the chain moves deterministically through \(1,2,3,0\), then repeats. Therefore it is at \(0\) after \(n\) steps exactly when \(n\) is a positive multiple of \(4\). In particular, \(p_{00}^{(4)}=1\) and \(p_{00}^{(8)}=1\), while \(p_{00}^{(n)}=0\) for positive \(n\) not divisible by \(4\). Thus \(R_0=\{4,8,12,\ldots\}\), and \(\gcd(4,8)=4\); every later return length is also divisible by \(4\), so \(d(0)=4\).
Check: The proposed period divides the first two return lengths, since \(4\mid4\) and \(4\mid8\). The deterministic progression shows no return length outside the multiples of \(4\), so no additional return can lower the gcd.
Worked Example: Early Return Lengths Give the Wrong Final GCD
On \(S=\{0,1,2,3,4\}\), let
The row sums are \(1\), \(\tfrac12+\tfrac12=1\), \(1\), \(\tfrac12+\tfrac12=1\), and \(1\), so this is a valid transition matrix. Starting at \(0\), the first step always goes to \(1\). From \(1\), the chain either returns immediately to \(0\), with probability \(\tfrac12\), or goes to \(2\), also with probability \(\tfrac12\). The latter route continues deterministically to \(3\); from \(3\), it goes to \(0\) with probability \(\tfrac12\), or to \(4\) with probability \(\tfrac12\), and \(4\) returns deterministically to \(0\). Consequently, the possible first-return lengths are \(2,4,5\), with respective probabilities \(\tfrac12,\tfrac14,\tfrac14\).
For clarity, the length-\(4\) probability includes two different paths. One is \(0\to1\to0\to1\to0\), with probability \(\tfrac12\cdot1\cdot\tfrac12\cdot1=\tfrac14\). The other is \(0\to1\to2\to3\to0\), with probability \(1\cdot\tfrac12\cdot1\cdot\tfrac12=\tfrac14\). Hence \(p_{00}^{(4)}=\tfrac14+\tfrac14=\tfrac12>0\). At length \(5\), the path \(0\to1\to2\to3\to4\to0\) has probability \(1\cdot\tfrac12\cdot1\cdot\tfrac12\cdot1=\tfrac14>0\), so \(p_{00}^{(5)}>0\). The length-\(2\) path has probability \(1\cdot\tfrac12=\tfrac12>0\), so \(p_{00}^{(2)}=\tfrac12\).
The gcd of the first two possible return lengths is \(\gcd(2,4)=2\). That is not the period: the later return length \(5\) changes the gcd, since \(\gcd(2,4,5)=1\). Every return from \(0\) is made by completing one or more of the described excursions, so its length is a sum of numbers from \(\{2,4,5\}\). Conversely, each of \(2,4,5\) is a return length. It follows that the gcd of all return lengths is exactly \(\gcd(2,4,5)=1\), and \(d(0)=1\).
Check: The exact return probabilities used above are \(p_{00}^{(2)}=\tfrac12\), \(p_{00}^{(4)}=\tfrac12\), and \(p_{00}^{(5)}=\tfrac14\). In particular, \(p_{00}^{(5)}>0\) confirms why the gcd \(2\) from lengths \(2\) and \(4\) was only provisional.
Worked Example: Two Return Lengths Fix the GCD
Consider the chain on \(S=\{0,1\}\) with
The row sums are \(0+1=1\) and \(\tfrac13+\tfrac23=1\). From state \(0\), the chain moves to \(1\) with probability \(1\). It returns to \(0\) at time \(2\) if the next move is \(1\to0\), so \(p_{00}^{(2)}=1\cdot\tfrac13=\tfrac13>0\). It returns at time \(3\) if the next two moves are \(1\to1\to0\), so \(p_{00}^{(3)}=1\cdot\tfrac23\cdot\tfrac13=\tfrac29>0\).
The gcd of these two return lengths is \(\gcd(2,3)=1\). Since the period divides every return length and is a positive integer, it must divide the gcd of any finite collection of return lengths. The only positive divisor of \(1\) is \(1\), so \(d(0)=1\). This is a finite certificate: no further return lengths can change the gcd below \(1\).
Check: The two path probabilities recompute to \(\tfrac13\) and \(\tfrac29\), both strictly positive, and \(2\) and \(3\) have no common positive divisor other than \(1\). Thus the calculated period is consistent with the definition.
A Reliable Procedure and a Common Pitfall
For an exact transition matrix, a practical calculation can proceed as follows:
Fix \(i\). A step length \(n\ge1\) belongs to \(R_i\) exactly when \(p_{ii}^{(n)}>0\); a probability of zero does not count as a possible return.
Use positive entries in powers of \(P\), or list positive-probability paths. Keep exact probabilities so that a small positive value is not confused with zero.
Take the gcd of the lengths found. It is a multiple of the true period. Continue until the available argument or structure certifies that no unseen return length can reduce it.
Common mistake. In the five-state example, observing returns at times \(2\) and \(4\) and declaring the period to be \(\gcd(2,4)=2\) is incorrect. The calculation is arithmetically correct for those two lengths but does not use the full return-time set: the length-\(5\) path has probability \(\tfrac14>0\). Including it gives \(\gcd(2,4,5)=1\). More generally, a finite sample gives an upper bound on the period in the divisibility sense—the period divides the sample gcd—but does not establish equality by itself.
The distinction matters whenever periods are being used to describe possible timing patterns of a chain. The gcd summarizes all possible return lengths, not merely the shortest return or the first few lengths discovered. A finite collection can settle the answer, as the finite-witness theorem proves, but a calculation must still justify why its collection is sufficient.
Check Your Understanding
For each question, distinguish a return length from a conclusion about the full return-time set.
- If \(R_i\) contains \(6\) and \(10\), what must be true of \(d(i)\), and what is the gcd of those two observed lengths?
- A state has possible return lengths \(3\), \(6\), and \(8\). Compute the gcd of these lengths and explain why the first two alone do not settle the same answer.
- For the two-state matrix in the third worked example, calculate the probability of the path \(0\to1\to1\to0\) and state its return length.
- Why does the finite-witness theorem not imply that checking the first two or first ten return lengths is always sufficient?
- If two positive-probability paths return to \(i\), one in \(m\) steps and one in \(n\) steps, explain why a return in \(m+n\) steps also has positive probability.