# Markov chain and classifying states

• Mar 16th 2009, 04:18 PM
PvtBillPilgrim
Markov chain and classifying states
Given the transition matrices below, find all communicating classes and classify all states:
The probabilities don't matter for this exercise, so I'm just going to put ones for non-zero entries, even though I know this is absurd mathematically:
(A)
1 1 0 1
1 0 0 1
1 0 0 0
1 0 1 0
I believe that the communicating classes are {1,2,4} and {3} and all these are ergodic.

(B)
1 1 1 1
0 0 1 1
1 0 1 0
0 0 1 0
I think the communicating classes are {1,3}, {2}, and {4}.
I'm not quite sure, but I believe states 1,3, and 4 are ergodic, and 3 is of period 2.

(C)
1 1 0 0
1 1 0 0
0 0 0 1
0 0 1 1
The communicating classes are {1,2} and {3,4} with {1,2} of period 2 and {3,4} ergodic.

Is this right? I think I have the communicating classes right, but I'm not sure about the state classifications. Thanks in advance for any help.
• Mar 17th 2009, 07:48 PM
meymathis
Quote:

Originally Posted by PvtBillPilgrim
Given the transition matrices below, find all communicating classes and classify all states:
The probabilities don't matter for this exercise, so I'm just going to put ones for non-zero entries, even though I know this is absurd mathematically:
(A)
1 1 0 1
1 0 0 1
1 0 0 0
1 0 1 0
I believe that the communicating classes are {1,2,4} and {3} and all these are ergodic.
I don't think this is correct. 1 can go to 1,2,4. 2 can go to 1,4. 3 can go to 1. 4 can go to 1 or 3. if 3 can go to 1 which can go to 4 which can go to 3, then 1 and 3 communicate. If 3 communicates with 1 which communicates with 2 and 4, then everything communicates with everything else. Another way to see this is dot product multiply the transition matrix 3 times with itself (X.X.X.X). This is the state matrix for taking 4 steps. You get (sorry for the python-ese):
[[16, 7, 4, 10],
[11, 5, 3, 7],
[ 7, 3, 2, 4],
[10, 4, 3, 6]]
This shows that after 4 steps, every state can go to any other state (since all non-zero). This shows that the whole space is in the same recurrent class. And thus the MC is irreducible.

This is aperiodic since X.X.X is non-zero everywhere :
[[7, 3, 2, 4],
[5, 2, 1, 3],
[3, 1, 1, 2],
[4, 2, 1, 3]]
And taken with the fact that X.X.X.X is non-zero everywhere and the GCD of 3 & 4 is 1. (i.e. you can get from any state to any other state in 3 steps, and you can in 4 steps. The GCD of 3 & 4 is 1, and thus the MC is aperiodic)

We have a finite MC that is irreducible and aperiodic. So it is ergodic.

(B)
1 1 1 1
0 0 1 1
1 0 1 0
0 0 1 0
I think the communicating classes are {1,3}, {2}, and {4}.
I'm not quite sure, but I believe states 1,3, and 4 are ergodic, and 3 is of period 2.
Again, your classes are not correct. Maybe you are misinterpreting what communicates mean. a communicates with b if you can get from a to b in some finite number of steps, and from b to a in some finite number of steps. See Markov chain - Wikipedia, the free encyclopedia. So I think you will find that this MC is also irreducible. 1 can go to all. 3 can get to 1. 2 & 4 can get to 1 via 3. As for periodicity, since 1 can go to 1, then its period is 1. The whole communicating class always has the same periodicity. Thus the MC is aperiodic. Thus it is ergodic. Just so you can see it more tangibly:
In [31]: x*x*x
Out[31]:
matrix([[6, 2, 9, 3],
[3, 1, 3, 1],
[4, 2, 6, 3],
[2, 1, 2, 1]])

In [32]: x*x*x*x
Out[32]:
matrix([[15, 6, 20, 8],
[ 6, 3, 8, 4],
[10, 4, 15, 6],
[ 4, 2, 6, 3]])
Again. Since all elements in either one shows that MC is irreducible. Since you can get from any state to any state in 3 or 4 steps, then the MC is aperiodic. Taken with the fact that it is finite, the MC is ergodic. You can try

(C)
1 1 0 0
1 1 0 0
0 0 0 1
0 0 1 1
The communicating classes are {1,2} and {3,4} with {1,2} of period 2 and {3,4} ergodic.

Is this right? I think I have the communicating classes right, but I'm not sure about the state classifications. Thanks in advance for any help.