Why Period Is Constant Within a Class

Why Period Is a Class Property

A Markov chain can return to a state only at certain step counts. The greatest common divisor of those counts is its period. At first, this appears to be a property of an individual state: different states can have different return paths, and their lists of return times need not look alike. Yet if two states communicate, a path from the first to the second and a path back let us transfer return paths between them. The added path lengths affect all those returns in a controlled way, which is enough to prove that the two greatest common divisors agree.

Let \((X_n)_{n\ge0}\) be a discrete-time 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: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Write \(p_{ij}^{(n)}\) for the \((i,j)\) entry of \(P^n\). A path of length \(n\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_n=j\) with \(p_{i_{r-1}i_r}>0\) for each step \(r\). Its probability, when started at \(i\), is the positive product \(\prod_{r=1}^n p_{i_{r-1}i_r}\).

For distinct communicating states, both connecting paths have positive length. Their concatenation is a positive-probability return path, so each state has at least one positive return length and its period is defined. If a state does not have any positive-probability return path, this definition does not assign it a period. For \(i=j\), equality of the periods is immediate whenever the period is defined.

The Path-Concatenation Argument

Proof. Concatenate the state sequences of the two paths, writing the shared state \(j\) only once. The resulting sequence has \(a+b\) steps. Its probability is the product of the probabilities of the two original paths: all transition probabilities are positive, so their product is positive. Thus the concatenated sequence is a positive-probability path from \(i\) to \(k\). For the matrix statement, the Chapman–Kolmogorov formula gives \(p_{ik}^{(a+b)}=\sum_{\ell\in S}p_{i\ell}^{(a)}p_{\ell k}^{(b)}\). The term with \(\ell=j\) is positive, and all terms are nonnegative, so the sum is positive. \(\square\)

Proof. If \(i=j\), the assertion is \(d(i)=d(i)\). Now suppose \(i\ne j\). Choose a positive-probability path from \(i\) to \(j\) of length \(a\ge1\), and a positive-probability path from \(j\) to \(i\) of length \(b\ge1\). By the lemma, \(a+b\) is a return length at \(i\), so \(d(i)\) divides \(a+b\). For any \(n\in R_j\), there is a positive-probability return path from \(j\) to itself of length \(n\). Concatenating the three paths gives a return path from \(i\) to itself of length \(a+n+b\). Therefore \(d(i)\) also divides \(a+n+b\). It follows that \(d(i)\) divides their difference \((a+n+b)-(a+b)=n\). This holds for every \(n\in R_j\), so \(d(i)\) is a common divisor of all the return lengths at \(j\). Hence \(d(i)\) divides their greatest common divisor \(d(j)\).

For the reverse divisibility, use a path from \(j\) to \(i\) of length \(b\) and one from \(i\) to \(j\) of length \(a\). Their concatenation gives a return length \(a+b\) at \(j\). For every \(m\in R_i\), inserting a return path of length \(m\) at \(i\) between those connecting paths gives a return length \(b+m+a\) at \(j\). Thus \(d(j)\) divides both \(a+b\) and \(b+m+a\), and hence divides their difference \(m\). It divides every member of \(R_i\), so \(d(j)\) divides \(d(i)\). The two positive integers divide each other, which implies \(d(i)=d(j)\). \(\square\)

The proof does not claim that two communicating states have identical return-time sets. In general they do not. Instead, the same connecting paths contribute the same fixed offset \(a+b\): the period at one state divides that offset and every offset return obtained by inserting a cycle at the other state. Taking differences removes the offset and yields divisibility of every return length.

Worked Examples

Common Pitfall: A First Return Is Not the Period

The first positive return length is only the smallest member of \(R_i\); the period is the greatest common divisor of all positive return lengths. In the last example, the shortest return from state \(1\) has length \(2\). A mistaken calculation would therefore report \(d(1)=2\). But the positive-probability path \(1\to2\to2\to1\) has length \(3\), and \(\gcd(2,3)=1\). The correct period is \(1\), in agreement with state \(2\).

Another error is to compare a return at \(j\) with a return at \(i\) without accounting for the lengths of the connecting paths. The proof uses the same paths of lengths \(a\) and \(b\) for every return length at \(j\). Both \(a+b\) and \(a+n+b\) are returns at \(i\); subtracting them isolates \(n\). Without this fixed offset argument, divisibility does not follow.

The result is useful because it lets us assign a single period to an entire communicating class rather than repeatedly computing it state by state. The class must be maximal in the definition: a proper subset whose states communicate is not, for that reason alone, a communicating class. Period equality applies to any two communicating states, while the class terminology refers to the full equivalence class.