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$
  • $\begingroup$ Hint (both cases): What are the lengths of the paths with positive probability from the state of your choice to itself? $\endgroup$ – Did Oct 2 '15 at 15:59
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$
  • $\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 Oct 3 '15 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 Oct 3 '15 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 Oct 3 '15 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 Oct 3 '15 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 Oct 3 '15 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.