markov chain help.

[mathman91]

Hi, just looking for clarification on something in plain English. If I have a probability transition matrix for states 1,2,3,4 given by:

[0.7 0 0.3 0 ]
[0.4 0.2 0.4 0 ]
[0.3 0 0.7 0 ]
[0.4 0 0.4 0.2]

If I'm asked to identify the recurrent and transient classes do I simply look at state 4 for example and see that the probability of returning to it from any other state is 0, so it's transient? And similarly say state 3, I can return to that from other states so it's recurrent? Also how would I deduce whether this matrix is periodic and reducible?

Thanks.

 

[BGM]

First a little arrangement of the states let you to have a better picture for the classification

\( \begin{matrix} 1 \\ 3 \\ 2 \\ 4 \end{matrix}
\begin{bmatrix} 0.7 && 0.3 && 0 && 0 \\
0.3 && 0.7 && 0 && 0 \\
0.4 && 0.4 && 0.2 && 0 \\
0.4 && 0.4 && 0 && 0.2 \end{bmatrix}\)

So it is easily see that states 1, 3 are not communicate with states 2, 4 and thus this markov chain is reducible.

A simple check for the aperiodic state is that you see the transition probabilities in the diagonal are non-zero, i.e. it is always possible to return to the same state in the next step.

If I'm asked to identify the recurrent and transient classes do I simply look at state 4 for example and see that the probability of returning to it from any other state is 0, so it's transient? And similarly say state 3, I can return to that from other states so it's recurrent?

The reasoning is completely correct. So if the question only ask you which state without proof, maybe this is enough for you to write them down immediately.

http://en.wikipedia.org/wiki/Markov_chain#Recurrence

A more formal argument is to check the definition. E.g. for state 2, because it is not accessible from other states as you have mentioned, so the first return time is either 1 or infinity (never return). So the sum = 0.2 < 1 which shows that it is transient.

For the class 1, 3, you can show that the \( f_{11}^{(n)}, f_{33}^{(n)} \) are just the geometric distribution pmf and of course the sum equals to 1, which means they are recurrent.

 

[mathy1991]

First a little arrangement of the states let you to have a better picture for the classification

\( \begin{matrix} 1 \\ 3 \\ 2 \\ 4 \end{matrix}
\begin{bmatrix} 0.7 && 0.3 && 0 && 0 \\
0.3 && 0.7 && 0 && 0 \\
0.4 && 0.4 && 0.2 && 0 \\
0.4 && 0.4 && 0 && 0.2 \end{bmatrix}\)

So it is easily see that states 1, 3 are not communicate with states 2, 4 and thus this markov chain is reducible.

A simple check for the aperiodic state is that you see the transition probabilities in the diagonal are non-zero, i.e. it is always possible to return to the same state in the next step.



The reasoning is completely correct. So if the question only ask you which state without proof, maybe this is enough for you to write them down immediately.

http://en.wikipedia.org/wiki/Markov_chain#Recurrence

A more formal argument is to check the definition. E.g. for state 2, because it is not accessible from other states as you have mentioned, so the first return time is either 1 or infinity (never return). So the sum = 0.2 < 1 which shows that it is transient.

For the class 1, 3, you can show that the \( f_{11}^{(n)}, f_{33}^{(n)} \) are just the geometric distribution pmf and of course the sum equals to 1, which means they are recurrent.

0.5 && 0.5 && 0 && 0 && 0 && 0 \\
0.3 && 0.7 && 0 && 0 && 0 && 0 \\
0 && 0 && 0.1 && 0 && 0.9 && 0 \\
0.25 && 0.25 && 0 && 0 && 0.25 && 0.25 \\
0 && 0 && 0.7 && 0 && 0.3 && 0 \\
0 && 0.2 && 0.2 && 0 && 0.2 && 0.4 \
What if this is my matrix? How do I deduce what are the communication classes? And which ones are transient and recurrent? Do I apply a similar argument to my first post? Thanks.

 

[BGM]

(Oh here the math tag do not allow a 6 column matrix; anyway I combine the column to display your matrix as follow

\( \left[ \begin{matrix} 0.5 && 0.5 && 0 && 0 && 0 \\
0.3 && 0.7 && 0 && 0 && 0 \\
0 && 0 && 0.1 && 0 && 0.9 \\
0.25 && 0.25 && 0 && 0 && 0.25\\
0 && 0 && 0.7 && 0 && 0.3 \\
0 && 0.2 && 0.2 && 0 && 0.2 \end{matrix} ~~~~
\begin{matrix}
0 \\ 0 \\ 0 \\ 0.25 \\ 0\\ 0.4
\end{matrix} \right]\)

To identify the communication classes, you need to look at those 0 entries. In the previous matrix, as what I arranged before, there is a 0 block matrix in the top right hand corner which indicate that the lower states are not accessible from the upper states, i.e. they are not communicating. Of course in this matrix you have another class.

For the transition and recurrence states problem you can follow from the previous arguments.

 

[mathy1991]

(Oh here the math tag do not allow a 6 column matrix; anyway I combine the column to display your matrix as follow

\( \left[ \begin{matrix} 0.5 && 0.5 && 0 && 0 && 0 \\
0.3 && 0.7 && 0 && 0 && 0 \\
0 && 0 && 0.1 && 0 && 0.9 \\
0.25 && 0.25 && 0 && 0 && 0.25\\
0 && 0 && 0.7 && 0 && 0.3 \\
0 && 0.2 && 0.2 && 0 && 0.2 \end{matrix} ~~~~
\begin{matrix}
0 \\ 0 \\ 0 \\ 0.25 \\ 0\\ 0.4
\end{matrix} \right]\)

To identify the communication classes, you need to look at those 0 entries. In the previous matrix, as what I arranged before, there is a 0 block matrix in the top right hand corner which indicate that the lower states are not accessible from the upper states, i.e. they are not communicating. Of course in this matrix you have another class.

For the transition and recurrence states problem you can follow from the previous arguments.

Oh right, thanks for you're help, by observing the matrix I have deduced that {1,2} is a communication class, I'm not sure if this is correct though, also {3,5} is another communication class I think? For transient states, state 4 seems to be the only one to satisfy this as it's the only state you cannot get to from a different state?

 

[BGM]

Both 4 and 6 are transient, because they are not accessible from {1, 3} nor {4, 6}, and the chain started from states 4 or 6 will eventually jump into either one of the recurrent classes {1, 3} or {4, 6}

 

[mathy1991]

Both 4 and 6 are transient, because they are not accessible from {1, 3} nor {4, 6}, and the chain started from states 4 or 6 will eventually jump into either one of the recurrent classes {1, 3} or {4, 6}

Okay thanks for your help, was I correct in observing the communication classes as {1,2} and {5,6}