Markov models and calculating the period of each state

Question

I am currently studying Markov models from the textbook Introduction to Modeling and Analysis of Stochastic Systems, second edition, by Kulkarni. I have just encountered the concept of periodicity in chapter 2:

Definition 2.4. (Periodicity). Let $\{ X_n, n \ge 0 \}$ be an irreducible DTMC on state space $S = \{1, 2, \dots, N \}$, and let $d$ be the largest integer such that

$$P(X_n = i \vert X_0 = i) > 0 \Rightarrow n \ \text{is an integer multiple of} \ d \tag{2.48}$$

for all $i \in S$. The DTMC is said to be periodic with period $d$ if $d > 1$ and aperiodic if $d = 1$.

So let's say we have a Markov chain with transition matrix $P$, and we want to find the period of each state. We then calculate $P^2, P^3, P^4, P^5, P^6$. It is found that $p_{ii} = p^3_{ii} = p^5_{ii} = 0$, and $p^2_{ii} \not= p^4_{ii} \not= p^6_{ii}$ and $p^2_{ii} > 0, p^4_{ii} > 0, p^6_{ii} > 0$. What can we conclude here? For the $n = 1, 3, 5$ cases, we would have that $d = 1$, right? But for the $n = 2, 4, 6$ case, I guess we would have that $d = 2$, right? So is this periodicity, or is it aperiodicity? And what specifically is meant by period of each state?

I would greatly appreciate it if people would please take the time to explain this.

Answer 1

An equivalent definition is:

$ d = gcd(n>0 : Pr(X_n = i | X_0 = i) >0) $

Gcd stands for the greatest common divisor.

If we want to apply this definition to your specific example, the answer would be either 1 or 2. If you could, further, prove that there are no odd length paths, the answer would be 2. If you could prove the opposite the answer would be 1. However, you can not claim anything before proving what the values for larger paths are.

Essentially, if the state is periodic, you can go around the path and get the to initial states only in multiple of period number of steps. The periodicity is very interesting property as all the states with the same period form an equivalence class of states that communicate. Furthermore, all the states within the class are either transient or recurrent.

I am not an expert on Markov chains, but I hope this helps!

Answer 2

Let us recall a few definitions first.

Let $i$ and $j$ be any two arbitrary states of a homogeneous Markov chain with finite state space $S$.

A state $j\in S$ is said to be accessible from state $i\in S$, if $p_{ij}^{(m)}>0$, for some positive integer $m\geq 1$. Symbolically, we express this as $i \rightarrow j$.

That is, having started in state $i$, the MC can reach state $j$ in $m$ steps. Though the state $j$ is accessible from state $i$, the state $i$ may or may not be accessible from state $j$. If state $i$ is also accessible from state $j$, then we say that states $i$ and $j$ communicate with each other. In terms of probabilities, states $i$ and $j$ communicate iff $p_{ij}^{(m)}$ and $p_{ji}^{(n)}$ for some positive integers $m,n\geq 1$. We express this as $i \leftrightarrow j$. A state $i$ may come back to itself if $p_{ii}^{(k)}>0$, for some positive integer $k\geq 1$.

The set of all states which communicates with each other form a communicating class.

The GCD of all those positive integers $n$, for which $p_{ii}^{(n)}>0$ is called the period of state $i$. A state with period $1$ is called aperiodic.

Periodicity is a class property. This means that, in a communicating class, if a state is aperiodic, then all states are aperiodic. Similarly, if a state in a communicating class has period $d$, then all the states in that class too have a period $d$.

A MC is said to be irreducible if all the states of that MC form a single communicating class. In an irreducible MC all states are either periodic or aperiodic. An irreducible MC can be either periodic or aperiodic depending on whether its states are periodic or not.

Thus, when we observe, $p_{ii}^{(1)}=p_{ii}^{(3)}=p_{ii}^{(5)}=0$, for some MC, it means that it is impossible for the MC to revisit state $i$, having started in state $i$ in exactly $1$, $3$, and $5$ steps.

We need to consider only those steps $n$ for which $p_{ii}^{(n)}>0$, to know about the periodicity value of a state.

For some MC, if $p_{ii}^{(2)}>0,\; p_{ii}^{(4)}>0,\;p_{ii}^{(6)}>0$, this means that the MC having started in state $i$, it again reaches the state $i$ only at steps $2,4$ and $6$. The GCD of these vales defines the period of the state $i$. Here, state $i$ is a periodic state with period $2$.

For some MC, it is possible that $p_{ii}^{(1)}=0,\; p_{ii}^{(2)}>0,\; p_{}^{(3)}>0$. In this case, the state $i$ is aperiodic.