# Homework Help: Probability- Markov Chains

1. Feb 5, 2012

### crazy_craig

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. Feb 5, 2012

### Ray Vickson

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

3. Feb 5, 2012

### crazy_craig

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.

4. Feb 6, 2012

### Ray Vickson

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

5. Feb 6, 2012

### crazy_craig

I finally got it. Thanks a ton, Ray!