Results 1 to 2 of 2

Math Help - Markov chain and classifying states

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    142

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2008
    Posts
    138
    Quote Originally Posted by PvtBillPilgrim View Post
    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.
    Comments in red.
    Last edited by meymathis; March 17th 2009 at 07:49 PM. Reason: fixed tpyo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Markov Chain of random variables from a primitive markov chain
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 19th 2011, 08:12 AM
  2. markov process and classification of states
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 18th 2011, 06:56 PM
  3. Markov Chains + Transient States Proof - Help
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 7th 2010, 07:40 AM
  4. Classifcation of Markov States, Convergence
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: September 23rd 2009, 04:07 PM
  5. Markov Chain: Transient and aperiodic states question
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: March 8th 2008, 12:17 PM

Search Tags


/mathhelpforum @mathhelpforum