Markov Chain Periodicity

Basic Concepts

The period of a state i of a Markov chain is defined as

where GCD represents the greatest common divisor of a set of integer values (see Coprime Numbers).

If d_i > 1, then i is periodic. If d_i = 1, then i is aperiodic.

Examples

Example 1: For the Markov chain with the transition matrix

We see that Pⁿ = P for even n, and Pⁿ = I for odd n. Thus p₁₁ⁿ = 0 for odd n and p₁₁ⁿ = 1 > 0 for even n. This means that d₁ = GCD(2, 4, 6, …) = 2. Similarly, d₂ = 2.

Similarly, for the transition matrix

d_i = 3 for i = 1, 2, 3.

Example 2: For the Gambler’s Ruin Markov chain, 0 and m are aperiodic since they are absorbing states. All the other states are periodic with d_i = 2.  p_ii¹ = p_ii³ = p_ii⁵ = 0. But p_ii² = pq > 0, p_ii⁴ = C(4,2)p²q² > 0, etc. Thus, d_i = GCD(2, 4, 6,…) = 2.

Example 3: The situation is similar for the random walk chain, except that there are no absorbing states. Thus, for any state i, d_i = 2.

Key Property

Property 1: All states in the same communications class (see Markov Chain Connectivity) have the same periodicity.

Proof: Suppose i ↔ j. Since i → j and j → i, there are k and m such that

By the Chapman-Kolmogorov Theorem (see Markov Chains Basic Concepts)

Thus, d_i | k+m. For any n such that p_jjⁿ > 0, by the Chapman-Kolmogorov Theorem is follows that

Thus, d_i | k+n+m. Since d_i | k+m and d_i | k+m+n, we conclude that d_i | n.

Since d_j = GCD(n: p_jjⁿ > 0), it follows that d_i ≤ d_j . Swapping the roles of i and j, we can prove that d_j ≤ d_i. Thus, d_i = d_j.

Links

↑ Markov chains

References

Aldridge, M. (2021) Class structure. Introduction to Markov Processes
https://mpaldridge.github.io/math2750/S07-classes.html

Norris, J. (2004) Discrete-time Markov chains. Cambridge University Press
https://www.statslab.cam.ac.uk/~jrn10//Markov/