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!

Probability- Markov Chains

  1. Feb 5, 2012 #1
    1. The problem statement, all variables and given/known data
    Six children (Dick, Helen, Joni, Mark, Sam, and Tony) play
    catch. If Dick has the ball he is equally likely to throw it to Helen,
    Mark, Sam, and Tony. If Helen has the ball she is equally likely to
    throw it to Dick, Joni, Sam, and Tony. If Sam has the ball he is
    equally likely to throw it to Dick, Helen, Mark, and Tony. If either
    Joni or Tony gets the ball, they keep throwing it to each other. If
    Mark gets the ball he runs away with it. (a) Find the transition
    probability and classify the states of the chain. (b) Suppose Dick
    has the ball at the beginning of the game. What is the probability
    Mark will end up with it?

    I only need help with (b). I created the transition matrix as below.
    2. Relevant equations

    So, by "ends", I'm assuming we want the lim n→∞ pn(x,y) = π(y), but I don't
    think that this chain converges (by raising this transition matrix to high powers), so there must be another way to solve this. It seems easy and I'm probably overlooking something. I've spent waay too long on this, so I'm asking for some help and a nudge in the right direction.

    Thank you very much!

    3. The attempt at a solution


    \begin{array}{cc}
    &D & H & J & M & S & T \\
    D& 0&.25&0&.25&.25&.25 \\
    H&.25&0&.25&0&.25&.25\\
    J&0&0&0&0&0&1\\
    M&0&0&0&1&0&0\\
    S&.25&.25&0&.25&0&.25\\
    T&0&0&1&0&0&0\\
    \end{array}
     
  2. jcsd
  3. Feb 5, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I don't know if you have taken "first-passage probabilities" yet, but that is what is involved in this problem. In case you have not yet seen this material, let me explain briefly.

    In the long run, the system either ends up in the set of states {J,T} or the single state {M}. That is, eventually, D, H and S are left forever, never to be re-visited. Furthermore, if state T (or J) is ever visited, states J and T together absorb the process; if state M is ever visited the state remains at M forever after. So, we want the probability that, starting from state D, the process eventually reaches state M. In this case, the limiting probabilities lim_{n}P^n(D,J) and lim_{n} P^n(D,T) do not exist because the states J and T are of period 2 (so for large n, these two probabilities just alternate between two fixed values). However, lim_{n} P^n(D,M) does exist, and that is what you are asked to find.

    Here is a hint about how to do it: let f(x) = lim_{n} P^n(x,M) for x = D, H and S. We want to find f(D), but to do that, we need to find also f(H) and f(S). We do that by getting 3 simple linear equations in the three unknowns f(D), f(H) and f(S). Think about starting from D ant taking one step. In order to reach M from D, we need to reach M from wherever we end up at in one step away from D. Similarly for starting from H and S. (Alternatively, you could just look at the limit of P^n(D,M) if you have some good way of taking matrix powers.)

    RGV
     
  4. Feb 5, 2012 #3
    Thanks for the quick reply!

    Most of what you said makes sense, and I used a calculator to find the limit of P^n(D,M), which is 2/5, but this is a little confusing to me:

    "Think about starting from D ant taking one step. In order to reach M from D, we need to reach M from wherever we end up at in one step away from D. ",

    and I'm not sure how to set up the system of linear equations.
     
  5. Feb 6, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Think of setting up the equations for limiting probabilities, except that now they can depend on the starting state. But, still, P^(n+1) = P.P^n, and you can look at what this becomes when n --> infinity (or at least, for those components that do have limits). Here, we just want to look at column M of P^infinity.

    RGV
     
  6. Feb 6, 2012 #5
    I finally got it. Thanks a ton, Ray!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Probability- Markov Chains
  1. Markov Chain (Replies: 1)

Loading...