Aperiodicity and the GCD of Return Times

Return Times and Their Greatest Common Divisor

A Markov chain can have a stationary distribution and still fail to approach it at each time step. One reason is that the chain may be restricted to a repeating schedule: for example, it may alternate between two groups of states. The period of a state records this timing constraint using the lengths of paths that return to that state. The key quantity is not one return time, but the greatest common divisor of all possible return times.

Let \((X_n)_{n\ge0}\) be a time-homogeneous Markov chain on a 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 each \(i\). Write \(p_{ii}^{(n)}=\mathbb{P}_i(X_n=i)\), where \(\mathbb{P}_i\) denotes the law of the chain started at \(i\). Its possible positive return times are the integers \(n\ge1\) for which \(p_{ii}^{(n)}>0\).

For an irreducible chain, every state has at least one possible positive return time: if there is more than one state, a path from \(i\) to another state and a path back give a return path; a one-state irreducible chain returns in one step. In a reducible chain, a state might have no possible return at all. In that case the displayed greatest common divisor is not defined, and we do not assign that state a period by this definition.

In an irreducible chain, states communicate: \(i\leftrightarrow j\) means that each can be reached from the other with positive probability in some finite number of steps. The following result explains why it makes sense to speak of the period of an irreducible class.

Proof. If \(i=j\), the claim is immediate. Otherwise, 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\). Their concatenation is a return path to \(i\) of length \(a+b\), so \(d(i)\) divides \(a+b\). Now take any possible return length \(r\ge1\) to \(j\). Concatenating the path from \(i\) to \(j\), a return path to \(j\) of length \(r\), and the path back to \(i\) gives a return path to \(i\) of length \(a+r+b\). Thus \(d(i)\) divides \(a+r+b\) as well, and hence divides their difference \(r\). Since this is true for every possible return length \(r\) to \(j\), \(d(i)\) divides \(d(j)\). Interchanging \(i\) and \(j\) gives \(d(j)\) divides \(d(i)\), so the positive integers are equal. \(\square\)

How Period One Removes a Timing Obstruction

Having period one means that the possible return times have no common divisor greater than one. This fact has a stronger consequence than merely having two return times with different parity: returns are possible at every sufficiently large integer time. The arithmetic fact behind this statement is recorded and proved next.

Proof. First choose a finite subset \(a_1,\ldots,a_k\) of \(A\) whose greatest common divisor is \(1\). Such a subset exists: enumerate members of \(A\), take successive greatest common divisors, and note that this is a nonincreasing sequence of positive integers. It can decrease only finitely often, and its eventual value is the greatest common divisor of \(A\), namely \(1\).

Set \(a=a_1\). Consider residues modulo \(a\) that can be represented by nonnegative integer sums of \(a_1,\ldots,a_k\). These residues include \(0\), and are closed under addition. They form the whole group of residues modulo \(a\): the integer combinations of \(a_1,\ldots,a_k\) include \(1\), since their greatest common divisor is \(1\); and any negative coefficient can be replaced, modulo \(a\), by a nonnegative coefficient by adding a sufficiently large multiple of \(a\) to that coefficient. (For the coefficient of \(a_1=a\), changing the coefficient does not change the residue.) Therefore, for each residue \(r\) modulo \(a\), choose a nonnegative sum \(c_r\) of \(a_1,\ldots,a_k\) with residue \(r\). There are only \(a\) residues, so \(N=\max_r c_r\) is finite. If \(n\ge N\) has residue \(r\), then \(n-c_r\) is a nonnegative multiple of \(a=a_1\). Consequently \(n=c_r+q a_1\) for some integer \(q\ge0\), a sum of members of \(A\). This proves the claim. \(\square\)

Return paths can be concatenated: if positive-probability paths return to \(i\) in \(u\) and \(v\) steps, their concatenation is a positive-probability return path in \(u+v\) steps. Therefore the lemma implies the following result for any state with period one.

Proof. Apply the lemma to the set of possible positive return times to \(i\). Every sufficiently large \(n\) is a sum of return times from that set. Concatenating the corresponding positive-probability paths gives a positive-probability return path of total length \(n\), which means \(p_{ii}^{(n)}>0\). \(\square\)

There is also a useful finite-state consequence. For an irreducible, finite-state chain with period one, some power \(P^{(n)}\) has every entry positive; in fact, every sufficiently large power does. This explains why aperiodicity is a standard hypothesis in convergence results: it removes a recurring time schedule that could prevent the transition probabilities from settling. This consequence alone is not a convergence theorem; hypotheses such as irreducibility and positive recurrence also matter in the relevant settings.

Proof. Fix a reference state \(r\). By the corollary, there is an integer \(L_0\) such that \(p_{rr}^{(L)}>0\) for every \(L\ge L_0\). For each \(i\), irreducibility gives a positive-probability path from \(i\) to \(r\), of some length \(a_i\ge0\); for each \(j\), it gives a path from \(r\) to \(j\), of some length \(b_j\ge0\). A length can be zero when the endpoints are \(r\). For any \(n\ge a_i+b_j+L_0\), set \(L=n-a_i-b_j\), so \(L\ge L_0\). Concatenate the chosen path from \(i\) to \(r\), a return path from \(r\) to \(r\) of length \(L\), and the chosen path from \(r\) to \(j\). This is a positive-probability path of length \(n\), so \(p_{ij}^{(n)}>0\). Since \(S\) is finite, the maximum of \(a_i+b_j+L_0\) over all pairs \(i,j\) is finite; take it as \(N\). Then the conclusion holds for every pair and every \(n\ge N\). \(\square\)

Worked Period Calculations

What Period One Does—and Does Not—Say

For an irreducible chain, the shared period is the class's common timing constraint. Period one removes that arithmetic constraint: returns are possible at all sufficiently large times, and, in a finite irreducible chain, so are transitions between every pair of states. This is the role of aperiodicity in convergence arguments. It does not by itself guarantee convergence or even a unique stationary distribution if other required conditions fail.

For example, consider the reducible chain on \(\{0,1\}\) with \(P=\begin{bmatrix}1&0\\0&1\end{bmatrix}\). Both rows sum to \(1\), and each state returns in one step, so each has period one. Yet an initial distribution \((\alpha,1-\alpha)\) stays \((\alpha,1-\alpha)\) at every time. Different initial distributions therefore do not approach a single common distribution. This example does not contradict convergence results that assume irreducibility: the two states do not communicate.

Common mistake. In the two-state chain from the second worked example, one might say that the period is \(2\) because the shortest return takes two steps. That calculation confuses the shortest return time with the greatest common divisor of all possible return times. The three-step path has probability \(\tfrac14>0\), so the return-time set contains both \(2\) and \(3\), and \(\gcd(2,3)=1\). The correct period is one.