Practical Tests for Aperiodicity

Practical Aperiodicity Tests

To determine the period of a state directly, one might try to list every possible return time. Practical tests avoid that task: a self-loop gives an immediate answer, and two return paths whose lengths are relatively prime are enough to establish aperiodicity. These tests concern the transition structure, not whether a class is recurrent or transient. One important qualification is that a period is defined only when the state has at least one possible positive-time return.

Throughout, let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with finite state space \(S\) and row-stochastic transition matrix \(P=(p_{ij})\). Thus \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\) and each row sums to \(1\). The natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Write \(\mathbb{P}_i\) for probabilities when \(X_0=i\). A positive-probability path of length \(m\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_m=j\) for which \(\prod_{\ell=0}^{m-1}p_{i_\ell i_{\ell+1}}>0\). Such a path implies \(\mathbb{P}_i(X_m=j)>0\).

A return path from \(i\) to itself has positive probability exactly when its product of transition probabilities is positive. In a finite chain, \(\mathbb{P}_i(X_n=i)>0\) holds exactly when at least one positive-probability return path of length \(n\) exists: the probability is a finite sum of nonnegative path probabilities, so it is positive precisely when one of those terms is positive. This lets us use paths in the transition graph to test membership in \(R_i\).

Three Tests and Why They Work

Proof. A self-loop is a return path of length \(1\), so \(1\in R_i\) when \(p_{ii}>0\). Any common divisor of the elements of \(R_i\) must divide \(1\), giving \(d(i)=1\). For the second claim, \(r,s\in R_i\), so \(d(i)\) divides both \(r\) and \(s\). If their greatest common divisor is \(1\), then \(d(i)=1\). The same argument applies to any finite collection of return lengths: \(d(i)\) divides every \(r_\ell\), and therefore divides their greatest common divisor. If that common divisor is \(1\), then \(d(i)=1\). \(\square\)

The tests provide sufficient ways to prove period one. If two found lengths have a common factor greater than one, that does not by itself establish the period: another return path might have a length not divisible by that factor. To prove a period greater than one, one must also rule out all return lengths not divisible by that period. For example, showing two return lengths are both even does not prove that every return length is even.

Proof. The case \(i=j\) is immediate. Suppose \(i\ne j\). Communication means there is a positive-probability path from \(i\) to \(j\), of some length \(r\ge1\), and one from \(j\) to \(i\), of some length \(s\ge1\). Concatenating them gives a positive-probability return path at \(i\) of length \(r+s\). For any \(n\in R_j\), choose a positive-probability return path at \(j\) of length \(n\). Concatenating the path from \(i\) to \(j\), this return path at \(j\), and the path from \(j\) to \(i\), gives a return path at \(i\) of length \(r+n+s\). Hence \(d(i)\) divides both \(r+s\) and \(r+n+s\), and so it divides their difference \(n\). This holds for every \(n\in R_j\), which implies \(d(i)\) divides \(d(j)\). Reversing the roles of \(i\) and \(j\) proves that \(d(j)\) divides \(d(i)\); the two positive integers are equal. Finally, if a communicating class has at least two states, every state \(i\) can reach another state \(j\) and be reached from \(j\), so their paths concatenate to a positive-length return path at \(i\). Thus its return-time set is nonempty. \(\square\)

The qualification about nonempty return-time sets matters for singleton classes. A singleton class may have a self-loop, in which case its period is \(1\), or it may have no self-loop and no possible return, in which case its period is undefined. A communicating class may also be transient: the period tests still apply if the states have return paths. Period describes possible return lengths, not the probability of returning eventually with probability \(1\).

Worked Tests on Finite Chains

Applying the Tests Carefully

A useful procedure is to work state by state or class by class. First identify which transitions have positive probability; zero-probability arrows cannot be used to construct return paths. Next check whether a state has any positive-length return path. If it does, look first for a self-loop. If there is none, search for two return paths with relatively prime lengths. When testing one state in an irreducible class with at least two states, the period-constancy result transfers the conclusion to every state in that class. A singleton class requires its own return-path check.

Sometimes the useful cycle is located at a different state. Suppose \(i\) can reach \(j\) along a positive-probability path of length \(r\), and \(j\) can reach \(i\) along one of length \(s\). A positive-probability return path at \(j\) of length \(c\) then gives return paths at \(i\) of lengths \(r+s\) and \(r+c+s\). Their difference is \(c\). This construction can help generate return lengths at \(i\), but it does not automatically prove that \(d(i)=1\): the greatest common divisor of the constructed lengths must actually be \(1\), or another valid test must apply.

Common mistake. Finding two return lengths with a common factor and concluding that the period equals that factor is not justified. For example, if a state has return paths of lengths \(4\) and \(6\), their greatest common divisor is \(2\), so the period must divide \(2\). But a return path of length \(5\), if one exists, forces the period to divide \(5\) as well, and then the period is \(1\). The correction is to use the two lengths only for what they prove: \(4\) and \(6\) alone do not establish a period of \(2\). To prove period \(2\), show that every possible return length is even and that at least one return length exists; to prove aperiodicity, it is enough to exhibit two relatively prime return lengths.

Aperiodicity is a structural property of return lengths. It is distinct from irreducibility, recurrence, and stationarity: an irreducible class can be periodic or aperiodic, and a transient irreducible class can also have a well-defined period. A state with no possible return is different again; without a nonempty return-time set, the gcd definition does not assign it a period. Keeping these distinctions explicit prevents a graph-based test from being applied outside its hypotheses.