Period One Means Aperiodic
A state can be revisited only at certain numbers of steps. If those possible return times share a common divisor greater than one, returns are restricted to a repeating schedule. If their greatest common divisor is one, the state has no such period-based restriction. This arithmetic distinction is the definition of aperiodicity; it does not require that every positive integer be a possible return time.
Throughout, 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, so \(\sum_{j\in S}p_{ij}=1\) for every \(i\in S\). Write \(P^n=(p_{ij}^{(n)})\) for the \(n\)-step transition matrix. A return at time \(n\) has positive probability from \(i\) precisely when \(p_{ii}^{(n)}>0\).
For an irreducible chain every state has a positive-time return: from \(i\), irreducibility gives a path to some state \(j\ne i\), if one exists, and a path back to \(i\); if the irreducible state space consists only of \(i\), its transition probability to itself is one. Thus the period is defined for every state in an irreducible chain. The earlier result that period is constant within a communicating class implies that an irreducible chain is aperiodic exactly when one (and hence every) state has period one.
The gcd is taken over all possible return lengths, not just the shortest one or a single observed one. For an infinite return-time set, it is still an ordinary positive integer: the common divisors of the set are divisors of any one fixed member, so only finitely many positive integers can be its gcd candidates.
Return Lengths Can Be Combined
Proof. By the Chapman–Kolmogorov equation, \(p_{ii}^{(m+n)}=\sum_{j\in S}p_{ij}^{(m)}p_{ji}^{(n)}\). Every term in this sum is nonnegative, and the term with \(j=i\) is \(p_{ii}^{(m)}p_{ii}^{(n)}>0\), because \(m,n\in D(i)\). Therefore \(p_{ii}^{(m+n)}>0\), so \(m+n\in D(i)\). \(\square\)
This proposition explains why the return-time set can contain many lengths even when only a few are needed to determine its gcd. For example, return lengths 2 and 3 imply returns at lengths 4, 5, 6, and other sums of 2s and 3s. The period, however, is already determined by \(\gcd(2,3)=1\).
Proof. If such a finite set exists, then \(d(i)=\gcd D(i)\) divides each \(n_k\), so it divides \(\gcd(n_1,\ldots,n_r)=1\). Since \(d(i)\) is positive, \(d(i)=1\). For the converse, suppose \(d(i)=1\). If \(D(i)\) is finite, its elements themselves are the required finite set. If it is infinite, enumerate its elements as \(n_1,n_2,\ldots\), and set \(g_r=\gcd(n_1,\ldots,n_r)\). Each \(g_{r+1}\) divides \(g_r\), and each \(g_r\) is a positive integer. A decreasing sequence of positive integers can have only finitely many strict decreases, so there is an \(R\) such that \(g_r=g_R\) for every \(r\ge R\). This stabilized value divides every \(n_k\), and every common divisor of all the \(n_k\) divides \(g_R\). Consequently \(g_R=\gcd D(i)=d(i)=1\). The finite set \(n_1,\ldots,n_R\) is the required witness. \(\square\)
The criterion is useful because one does not need to enumerate the full return-time set. Finding two return lengths with gcd one is enough; if two do not suffice, a third or later return length may reduce the gcd to one. Conversely, a few lengths whose gcd is greater than one do not establish periodicity unless they account for all possible return lengths or otherwise show that every return length shares that divisor.
Worked Return-Time Calculations
Worked Example: A Two-State Alternating Chain
Consider a chain on \(S=\{1,2\}\) with transition matrix \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Both rows sum to \(1\), and the chain alternates deterministically between the two states. Starting from state 1, it returns to 1 after 2 steps, then after 4 steps, and so on. It cannot return after an odd number of steps, since after every odd number of transitions it is at state 2. Therefore \(D(1)=\{2,4,6,\ldots\}\), and \(d(1)=\gcd(2,4,6,\ldots)=2\). By the same alternation, \(D(2)=\{2,4,6,\ldots\}\) and \(d(2)=2\). This irreducible chain is periodic, not aperiodic.
Check: \(P^2\) is the identity matrix, so \(p_{11}^{(2)}=p_{22}^{(2)}=1\), while \(P\) has zero diagonal entries. Even powers permit returns and odd powers do not, in agreement with the calculated return-time sets.
Worked Example: Return Lengths Two and Three
Let \(S=\{0,1,2\}\) and \(P=\begin{bmatrix}0&1&0\\ \tfrac12&0&\tfrac12\\ 1&0&0\end{bmatrix}\). The row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(1+0+0=1\). The chain is irreducible: \(0\) reaches \(1\), \(1\) reaches \(2\), and \(2\) reaches \(0\), so each state can reach the others by following these transitions.
From state 0, every return begins \(0\to1\). At state 1, the chain either goes directly to 0, completing a return in 2 steps with probability \(\tfrac12\), or goes to 2 and then to 0, completing a return in 3 steps with probability \(\tfrac12\cdot1=\tfrac12\). Repeating these choices shows that \(D(0)=\{2a+3b:a,b\ge0,\ a+b\ge1\}\). In particular, \(2\in D(0)\) and \(3\in D(0)\), so \(d(0)\) divides \(\gcd(2,3)=1\), and hence \(d(0)=1\).
For completeness, state 1 has return lengths 2 and 3: \(1\to0\to1\) has length 2, and \(1\to2\to0\to1\) has length 3. Thus \(d(1)=1\). State 2 has return lengths 3 and 5: \(2\to0\to1\to2\) has length 3, and \(2\to0\to1\to0\to1\to2\) has length 5. Since \(\gcd(3,5)=1\), \(d(2)=1\). Therefore the whole irreducible chain is aperiodic.
Check: The two-step return probability from 0 is \(p_{00}^{(2)}=p_{01}p_{10}=1\cdot\tfrac12=\tfrac12>0\). The three-step return probability is \(p_{00}^{(3)}=p_{01}p_{12}p_{20}=1\cdot\tfrac12\cdot1=\tfrac12>0\). These exact positive probabilities verify the two return lengths used to certify period one.
Worked Example: Three Known Return Lengths
Suppose a state \(i\) in a discrete-time chain is known to have positive-probability returns at lengths 6, 10, and 15. The full return-time set need not be known to decide whether \(i\) is aperiodic. First, \(\gcd(6,10)=2\). Then \(\gcd(2,15)=1\), so \(\gcd(6,10,15)=1\). The period \(d(i)\) divides all three known return lengths, hence divides their gcd, which is 1. Thus \(d(i)=1\), and \(i\) is aperiodic.
Check: The finite-witness criterion applies because each of 6, 10, and 15 is assumed to belong to \(D(i)\), not merely to be a length at which the chain might be observed. Their gcd is exactly 1, so no additional return lengths need to be found.
Worked Example: Aperiodicity Depends on the Class
Consider a chain on \(S=\{1,2,3,4,5\}\) with transition matrix \(P=\begin{bmatrix}0&1&0&0&0\\1&0&0&0&0\\0&0&0&1&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}\). The five row sums are each \(1\). States 1 and 2 form one communicating class and alternate, so their return-time sets are \(\{2,4,6,\ldots\}\) and their periods are 2. States 3, 4, and 5 form another class and cycle in that order, so their return-time sets are \(\{3,6,9,\ldots\}\) and their periods are 3. This chain is reducible and has no single common period across its classes; it is not a chain in which every state is aperiodic.
Check: The first block returns to its starting state after exactly the positive even lengths, whose gcd is 2. The second block returns after exactly positive multiples of 3, whose gcd is 3. Thus neither class has period one.
Interpreting Aperiodicity Carefully
Aperiodicity is a property of the return-time arithmetic, not a claim that the chain returns at every step. In the three-state example, state 0 cannot return in one step, yet return lengths 2 and 3 already give period one. Conversely, having a return at one particular length does not by itself settle the period: the return lengths 2, 4, and 6 alone have gcd 2, while adding a return length of 3 changes the gcd to 1.
For an irreducible chain, the period is shared by all states in its communicating class, as established in the earlier material on periods within a class. Therefore it is enough to find a finite collection of return lengths for one state whose gcd is one. For a reducible chain, different communicating classes can have different periods, as the last example shows; check the classes or the individual states rather than assuming a single period applies throughout.
Common mistake. In the three-state example, using only the return length 2 at state 0 and writing \(d(0)=2\) is incorrect: that calculation treats one return length as if it were the complete return-time set. The chain also returns in 3 steps, with positive probability \(\tfrac12\). The corrected calculation is \(d(0)=\gcd(2,3,\ldots)=1\), since the gcd of the full set must divide both 2 and 3. A finite subset with gcd one proves aperiodicity; a finite subset with gcd greater than one does not prove that the full set has that gcd.
Check Your Understanding
For each question, identify the return lengths being used and compute the gcd before deciding whether the state is aperiodic.
- A state has possible return lengths \(4,8,12,\ldots\). What is its period?
- A state has positive-probability returns at lengths 4 and 7. What does the finite-witness criterion imply?
- Why does knowing that 6 and 10 are return lengths not, by itself, establish that a state's period is 2?
- In an irreducible chain, why can a finite set of return lengths for one state be enough to establish aperiodicity of the chain?
- Can a state be aperiodic even if a one-step return is impossible? Explain using a pair of return lengths.