1
$\begingroup$

A class property of Markov Chain is periodicity. But I do not understand how is to calculate the period of a state from a transition probability matrix.

I am following the book "An Introduction to Stochastic Modeling" by Howard M. Taylor and Samuiel Karlin.

In the book there are some examples on periodicity of a Markov Chain but I don't understand. Following I am giving two examples :

$(1)$ In a finite Markov chain of $n$ states with transition matrix $$P= \begin{bmatrix} 0 & 1 & 0&0&\ldots&0 \\ 0 &0 & 1&0&\ldots&0 \\ \vdots\\ 0 & 0 &&&\ldots&1 \\ 1 & 0 & 0&&\ldots&0 \\ \end{bmatrix}, $$

each state has period $n$. But how can I understand that it has period $n$?

$(2)$ A Markov chain has the transition probability matrix

$$P= \begin{bmatrix} 0 & 0 & 0.8 &0.2\\ 0 & 0 & 0.4 &0.6\\ 0.7 & 0.3 & 0 &0\\ 0.2 & 0.8 & 0 &0\\ \end{bmatrix}. $$

All states are periodic with period $2$. But why is the period $2$ here ?

Any help is appreciated. Thank you.

$\endgroup$
1
  • $\begingroup$ Hint (both cases): What are the lengths of the paths with positive probability from the state of your choice to itself? $\endgroup$
    – Did
    Commented Oct 2, 2015 at 15:59

1 Answer 1

Reset to default
2
$\begingroup$

a) In the first case, if we try to make the respective graph, we will end up with a circle graph, i.e. the transition is of the form: $$1\to 2\to \cdots \to (n-1)\to n\to 1\to \cdots .$$ Assuming that we start from any state $i,\,i = 1,\ldots, n$ we can reach the same state $i$ after exactly $k\cdot n,\, (k \in \mathbb Z^+)$ steps and considering the definition of the period of a state we have that the period $d$ for the state $i$ is $d_i = n,\, i = 1,\ldots,n$ (basically, it's an irreducible markov chain, so all the states will have the same period).

b) We can observe that we have an irreducible Markov chain, thus every state is going to have the same period. Notice that we have the following pattern: $$\{1,2\}\to \{3,4\}\to\{1,2\}\to\{3,4\}\to \cdots.$$ What does this tell you about the periodicity of each state?

$\endgroup$
7
  • $\begingroup$ One more question: $P= \begin{bmatrix} 0 & 1 & 0 &0\\ 0 & 0 & 1 &0\\ 0& 0& 0 &1\\ 0.5 & 0 & 0.5 &0\\ \end{bmatrix}. $ I guessed the period of state $0$, $d(0)=4$. But it is actually $2$. Why? $\endgroup$
    – ABC
    Commented Oct 3, 2015 at 0:44
  • $\begingroup$ Firstly, is it irreducible? If yes, all the states are going to have the same period. Secondly, how is the period of a state defined? Also, try to make the respective graph and find the cyclic subclasses. $\endgroup$
    – thanasissdr
    Commented Oct 3, 2015 at 0:47
  • $\begingroup$ yes, this is irreducible markov chain. so all states have the same period. state 3 has period 2, so necessarily state 0 will have also period 2. But if before looking at irreducibiility, if i only concentrate on the particular 0 state, then I can't find out the right periodicity. for period, we need to take the greatest common divisor(g.c.d.), and it looks for state 0, I am coming to state 0 after exactly $4*k,(k=1,2,,\ldots)$ steps. $\endgroup$
    – ABC
    Commented Oct 3, 2015 at 0:56
  • $\begingroup$ Nope, that's not true. Starting from state $0$ (I am used to saying state $1$ rather than $0$), we can reach it again also in $6$ steps, i.e. $1\to 2\to 3\to 4\to 3\to 4\to 1$. Thus: $$\gcd\{4,6,8,10,12,\ldots \}=2.$$ $\endgroup$
    – thanasissdr
    Commented Oct 3, 2015 at 1:01
  • $\begingroup$ how did you make the diagram? After $1\to2\to3\to4$, then why is it again $3$, and then $4$ ? $\endgroup$
    – ABC
    Commented Oct 3, 2015 at 1:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .