A state in a discrete-time Markov chain is periodic if the chain can return to the state only at multiples of some integer larger than 1. Periodic behavior complicates the study of the limiting behavior of the chain. As we will see in this section, we can eliminate the periodic behavior by considering the \( d \)-step chain, where \( d \in \N_+ \) is the period, but only at the expense of introducing additional equivalence classes. Thus, in a sense, we can trade one form of complexity for another.
As usual, our starting point is a (time homogeneous) discrete-time Markov chain \( \bs{X} = (X_0, X_1, X_2, \ldots) \) with (countable) state space \( S \) and transition probability matrix \( P \).
The period of state \( x \in S \) is \[ d(x) = \gcd\{n \in \N_+: P^n(x, x) \gt 0 \} \] State \( x \) is aperiodic if \( d(x) = 1 \) and periodic if \( d(x) \gt 1 \).
Thus, starting in \( x \), the chain can return to \( x \) only at multiples of the period \( d \), and \( d \) is the largest such integer. Perhaps the most important result is that period, like recurrence and transience, is a class property, shared by all states in an equivalence class under the to and from relation.
If \( x \leftrightarrow y \) then \( d(x) = d(y) \).
Suppose that \( x \leftrightarrow y \). The result is trivial if \( x = y \), so let's assume that \( x \neq y \). Recall that there exist \( j, \, k \in \N_+ \) such that \( P^j(x, y) \gt 0 \) and \( P^k(y, x) \gt 0 \). But then \( P^{j+k}(x, x) \ge P^j(x, y) P^k(y, x) \gt 0 \) and hence \( d(x) \mid (j + k) \). Suppose now that \( n \) is a positive integer with \( P^n(y, y) \gt 0 \). Then \( P^{j+k+n}(x, x) \ge P^j(x, y) P^n(y, y) P^k(y, x) \gt 0 \) and hence \( d(x) \mid (j + k + n) \). It follows that \( d(x) \mid n \). From the definition of period, \( d(y) \mid d(x) \). Reversing the roles of \( x \) and \( y \) we also have \( d(x) \mid d(y) \). Hence \( d(x) = d(y) \).
Thus, the definitions of period, periodic, and aperiodic apply to equivalence classes as well as individual states. When the chain is irreducible, we can apply these terms to the entire chain.
Suppose that \( x \in S \). If \( P(x, x) \gt 0 \) then \( x \) (and hence the equivalence class of \( x \)) is aperiodic.
By assumption, \( 1 \in \{n \in \N_+: P^n(x, x) \gt 0\} \) and hence the greatest common divisor of this set is 1.
The converse is not true, of course. A simple counterexample is given in .
Suppose now that \( \bs{X} = (X_0, X_1, X_2, \ldots) \) is irreducible and is periodic with period \( d \). There is no real loss in generality in assuming that the chain is irreducible, for if this were not the case, we could simply restrict our attention to one of the irreducible equivalence classes. Our exposition will be easier and cleaner if we recall the congruence equivalence relation modulo \( d \) on \( \Z \), which in turn is based on the divison partial order. For \( n, \, m \in \Z \), \( n \equiv_d m \) if and only if \( d \mid (n - m) \), equivalently \( n - m \) is an integer multiple of \( d \), equivalently \( m \) and \( n \) have the same remainder after division by \( d \). The basic fact that we will need is that \( \equiv_d \) is preserved under sums and differences. That is, if \( m, \, n, \, p, \, q \in \Z \) and if \( m \equiv_d n \) and \( p \equiv_d q \), then \( m + p \equiv_d n + q \) and \( m - p \equiv_d n - q \).
Now, we fix a reference state \( u \in S \), and for \( k \in \{0, 1, \ldots, d - 1\} \), define \[ A_k = \{x \in S: P^{n d + k}(u, x) \gt 0 \text{ for some } n \in \N\} \] That is, \( x \in A_k \) if and only if there exists \( m \in \N \) with \( m \equiv_d k \) and \( P^m(u, x) \gt 0 \).
Suppose that \( x, \, y \in S \).
Suppose first that \( x \in A_k \). By definition, \( u \) leads to \( x \) in \( m \) steps for some \( m \equiv_d k \). Since the chain is irreducible, \( x \) leads back to \( u \), say in \( p \) steps. It follows that \( u \) leads back to \( u \) in \( m + p \) steps. But because \( u \) has period \( d \), we must have \( m + p \equiv_d 0\) and hence \( p \equiv_d -k \).
Next suppose that \( x \in A_j \) and \( y \in A_k \). We know that \( u \) leads to \( x \) in \( m \) steps for some \( m \equiv_d j \), and we now know that \( y \) leads to \( u \) in \( p \) steps for some \( p \equiv_d -k \). Since the chain is irreducible, \( x \) leads to \( y \), say in \( n \) steps. It follows that \( u \) leads back to \( u \) in \( m + n + p \) steps. Again, since \( u \) has period \( d \), \( m + n + p \equiv_d 0 \) and it follows that \( n \equiv_d k - j \)
Next, note that since the chain is irreducible and since \(\{0, 1, \ldots, d - 1\}\) is the set of all remainders modulo \( d \), we must have \( \bigcup_{i=0}^{d-1} A_i = S \). Suppose that \( x, y \in S \) and \( P^n(x, y) \gt 0 \) for some \( n \in \N \). Then \( x \in A_j \) and \( y \in A_k \) for some \(j, \, k \in \{0, 1, \ldots\}\). By the same argument as the last paragraph, we must have \( n \equiv_d k - j \).
All that remains is to show that the sets are disjoint, and that amounts to the same old argument yet again. Suppose that \( x \in A_j \cap A_k \) for some \( j, \, k \in \{0, 1, \ldots, d - 1\} \). Then \( u \) leads to \( x \) in \( m \) steps for some \( m \equiv_d j \) and \( x \) leads to \( u \) in \( n \) steps for some \( n \equiv_d - k \). Hence \( u \) leads back to \( u \) in \( m + n \) steps. Since the chain has period \( d \) we have \( m + n \equiv_d 0 \) and therefore \( j - k \equiv_d 0 \). Since \( j, \, k \in \{0, 1, \ldots, d - 1\} \) it follows that \( j = k \).
\( (A_0, A_1, \ldots, A_{d-1}) \) are the equivalence classes for the \( d \)-step to and from relation \( \underset{d}{\leftrightarrow} \) that governs the \( d \)-step chain \( (X_0, X_d, X_{2 d}, \ldots) \) that has transition matrix \( P^d \).
The sets \( (A_0, A_1, \ldots, A_{d-1}) \) are known as the cyclic classes. The basic structure of the chain is shown in the state diagram below:
Consider the Markov chain with state space \( S = \{a, b, c\} \) and transition matrix \( P \) given below:
\[ P = \left[\begin{matrix} 0 & \frac{1}{3} & \frac{2}{3} \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}\right] \]Consider the Markov chain with state space \( S = \{1, 2, 3, 4, 5, 6, 7\} \) and transition matrix \( P \) given below:
\[ P = \left[\begin{matrix} 0 & 0 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} & 0 & 0 \\ 0 & 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{3} & \frac{2}{3} \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & \frac{3}{4} & \frac{1}{4} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 & 0 \end{matrix}\right] \]
The following special models are studied in separate section: