A state in a 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) 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 \} \]Thus, starting in \( x \), the chain can return to \( x \) only at multiples of the period \( d \), and \( d \) is the largest such integer. State \( x \) is aperiodic if \( d(x) = 1 \) and periodic if \( d(x) \gt 1 \). Perhaps the most important result is that period, like recurrence and transience, is a class property.
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 \). 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. Sketch a state diagram to show that the converse of is not true.
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 closed, irreducible equivalence classes. 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\} \]Suppose that \( j, \; k \in \{0, 1, \ldots, d - 1\} \) and \( x, \; y \in S \). Then \( x \in A_j \) and \( y \in A_k \) if and only if \( P^n(x, y) \gt 0 \) for some \( n = (k - j) \mod d \).
\( (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 \).
In particular, \( (A_0, A_1, \ldots, A_{d-1}) \) is a partition of the state space \( S \); these sets 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 = \{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] \]Review the definition of the basic Ehrenfest chain. Show that this chain has period 2, and find the cyclic classes.
Review the definition of the modified Ehrenfest chain. Show that this chain is aperiodic.
Review the definition of the simple random walk on \( \Z^k \). Show that the chain is periodic with period 2, and find the cyclic classes.