1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Markov chain chance one state is reached before another

  1. Jul 29, 2013 #1
    Hey could someone explain why this is true? I am trying to understand how to solve such a problem but I don't understand the solution.

    Problem:
    Given a Markov chain [itex]\left\{X_{n}: n\in\ \mathbb{N}\right\}[/itex] with four states 1,2,3,4 and transition matrix
    [itex]P =
    \begin{pmatrix}
    0 & \frac{1}{2}& \frac{1}{2} & 0 \\
    0 & 0 & \frac{1}{2} & \frac{1}{2}\\
    \frac{1}{2} & 0 & 0 & \frac{1}{2} \\
    \frac{1}{2} & \frac{1}{2} & 0 & 0
    \end{pmatrix}[/itex]
    We leave from state 3. What is the chance that state 1 will be reached before state 4?

    Solution:
    Lets call this chance x. Lets call y the same chance but instead leaving from 2. Lets call:
    [itex]f =
    \begin{pmatrix}
    1 \\
    x \\
    y \\
    0
    \end{pmatrix}[/itex]
    Then f satisfies P'f = f with P' the transition matrix derived from P by making state 1 and 4 absorbing states i.e.,

    [itex]
    \begin{pmatrix}
    1 & 0& 0 & 0 \\
    0 & 0 & \frac{1}{2} & \frac{1}{2}\\
    \frac{1}{2} & 0 & 0 & \frac{1}{2} \\
    0 & 0 & 0 & 1\end{pmatrix}*\begin{pmatrix}
    1 \\
    x \\
    y \\
    0
    \end{pmatrix}= \begin{pmatrix}
    1 \\
    x \\
    y \\
    0
    \end{pmatrix}[/itex]
    Solving gives y = 1/2, x = 1/4.
     
    Last edited: Jul 29, 2013
  2. jcsd
  3. Jul 29, 2013 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You need to be more specific: what part do you not understand?

    What you presented above is pretty standard, and is almost always part of the course material regarding Markov chains.

    Also: for context: are you using a textbook and/or course notes? Do these sources not have such material in them?
     
  4. Jul 29, 2013 #3
    If you could direct me to a place where this is explained I would be grateful. The material my teacher provided doesn't address this problem or atleast not directly, so I find it hard to understand this solution from the theory provided. I dont understand why P'f=f must be true. And I dont understand why those states are made absorbing.

    Edit: I dont understand why its necessary to multiply with such a vector either.
     
    Last edited: Jul 29, 2013
  5. Jul 29, 2013 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    When you don't understand something, it is a good idea to work it out from first principles. Let's do that.

    Define ##f_i(n)## to be the probability that, starting from state i we reach state 1 for the first time at time n and do not reach state 4 before time n; let ##f_i = \sum_{n=1}^{\infty} f_i(n)##; this is the probability we reach state 1 before reaching state 4, starting from state i.

    Note that
    [tex] f_i(n) = P\{X_1 \neq 1,4, \: X_2 \neq 1,4,\: \ldots, X_{n-1} \neq 1,4, \: X_n = 4 |X_0=i\} [/tex]
    Conditioning on ##X_1## we have
    [tex] f_i(n) = \sum_{j \neq 1,4} p_{ij} P\{X_2 \neq 1,4, \: \ldots, X_{n-1} \neq 1,4,\: X_n = 1 |X_1 = j, X_0 = i \} \\
    = \sum_{j \neq 1,4} p_{ij} f_j(n-1).[/tex]
    Also: ##f_i(1) = p_{i1}##. Summing over n we get
    [tex] f_i = f_i(1) + \sum_{n=2}^{\infty} f_i(n)\\
    = p_{ij} + \sum_{j \neq 1,4} p_{ij} \sum_{n=2}^{\infty} f_j(n-1)
    = p_{i1} + \sum_{j \neq 1,4} p_{ij} f_j .[/tex]

    In other words:
    [tex] f_2 = p_{21} + p_{22} f_2 + p_{23} f_3 \\
    f_3 = p_{31} + p_{32} f_2 + p_{33} f_3.[/tex]
    Note that this is a simple 2x2 linear system that we can solve easily.

    Of course, since (in this example, but not all examples) we either reach state 1 before state 4 or reach state 4 before state 1, the probability that, starting from state i we reach 4 before 1 is just ## 1 - f_i##.

    Note that if we set ##f_1 = 1## and ##f_4 = 0## we can write the equations above as
    [tex] f_1 = 1 f_1 + 0 f_2 + 0 f_3 + 0 f_4 \\
    f_2 = p_{21} f_1 + p_{22}f_2 + p_{23} f_3 + p_{24}f_4\\
    f_3 = p_{31} f_1 + p_{32}f_2 + p_{33}f_3 + p_{34} f_4 \\
    f_4 = 0 f_1 + 0 f_2 + 0 f_3 + 1 f_4[/tex]
    This is just the set of equations ##f = \tilde{P} f## for a modified Markov chain with transition matrix
    [tex]\tilde{P} = \pmatrix{1 &0&0&0\\p_{21}&p_{22} & p_{23} & p_{24}\\
    p_{31} & p_{32} & p_{33} & p_{34} \\
    0 & 0 & 0 & 1}[/tex]
    and with
    [tex] f = \pmatrix{1 \\f_2 \\f_3 \\0}[/tex]

    As I said: work it out in detail from first principles.
     
  6. Jul 30, 2013 #5
    Thank you very much for taking your time and explaining this neatly and thoroughly. I'm sure this will be helpful to many others too as I haven't found an explanation of this particular problem trough Google.
     
  7. Jul 30, 2013 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    There was a typo in my post, which I corrected in an "edit" and which was seemingly accepted, but was later not implemented. I should have written ##X_n = 1## instead of ##X_n = 4## n the definition of ##f_i(n)##.
     
  8. Jul 30, 2013 #7
    Yes I realized that. What about the solution? Doesn't it also contain a mistake? If x is the chance leaving from state 3 shouldnt it come in the third place of the vector instead of the second?
     
  9. Aug 2, 2013 #8
    I'm sorry but as I know sometimes replies are overlooked I'm sending another reply with the hope you will respond.
     
  10. Aug 2, 2013 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If you are asking me to check whether a given pair of numbers is the solution of a given pair of two simple linear equations in two unknowns, then I refuse to answer. You can check it yourself---and you always should, as a matter of habit, in such cases. Just plug in the numbers to see if they work. If they don't work, somebody has made an error---typographical or otherwise---and you need to re-solve those equations.
     
  11. Aug 2, 2013 #10
    Well the pair is a solution to that matrix vector multiplication. But I'm pretty sure the teacher made a mistake in putting the chance x on the second place of the vector, since the way u explained it it should be on the third place. This is because x is the chance leaving from state 3. I just wanted to make sure I understood that correctly.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Markov chain chance one state is reached before another
Loading...