1

Markov chain.png

Ok so we have the above Markov chain and all of the transitions coming out of a vertex are equal( $p_{12}=p_{11}=1/2, p_{21}=p_{23}=1/2, p_{31}=p_{32}=p_{34}=1/3 $ and $p_{41}=1 $

Ok so how can we find the probability to visit node 2 exactly two times before we visit node 4, if $X_0=1$ ??

I really have no idea how to calculate this since node 1 has a self loop and the number of paths that visit 2 exactly two times before visiting node 4 is infinite.. Any ideas?

Mario Zelic
  • 319
  • Start with simple cases, say 1,2,(1or3),2,4 and compare that to all other 4 step paths. Then try all 5 step paths. Code it up numerically and estimate the probability that way. It will at least give a feel for the solution. – jdods Dec 19 '17 at 14:31
  • yes but since we have a self loop on node 1, the number of paths is infinite my friend. It does not matter after how many steps we visit node 4, we only care about visiting node 2 exactly two times before we visit 4 for the first time. – Mario Zelic Dec 19 '17 at 14:34
  • Yes, but I mean to calculate the relative probability for certain finite step paths, e.g. conditioning on total number of steps. Just to get a feel for the answer, of course it won't be the answer. – jdods Dec 19 '17 at 14:38

1 Answers1

1

One approach is to make a list of all the infinitely many paths that visit $2$ exactly twice and then get to $4$.

These are:

  • $1 \dots 1 2 1 \dots 1 2 3 4$,
  • $1 \dots 1 2 3 1 \dots 1 2 3 4$, and
  • $1 \dots 1 2 3 2 3 4$,

where each block of $1$'s can have an arbitrary number of $1$'s in it, but at least one. Then compute the probability of following each path. For example, $$ \Pr[\underbrace{1 \dots 1}_k 2 3 2 3 4] = (\tfrac12)^k \cdot \tfrac12 \cdot \tfrac13 \cdot \tfrac12 \cdot \tfrac13. $$ Sum all the probabilities (which involves taking the sum of a geometric series) and you get the answer you want.

Another approach avoids looking at each individual path.

From node $1$, you will eventually go to node $2$. It doesn't really matter how, as long as you get there.

From node $2$, you will either leave and come back to node $2$, or you will leave and get to node $4$. If $p$ is the probability that you leave $2$ and get to node $4$ before you come back, then the probability that you visit node $2$ exactly twice is $(1-p)p$: the first time, you come back, and the second time, you don't.

But $p$ is not hard to figure out: the only way to get from node $2$ to node $4$ without ever coming back to $2$ is to go from $2$ directly to $3$ and then to $4$.

More generally,the probability that you visit node $2$ exactly $k$ times before you see $4$, for any $k\ge 1$, is $(1-p)^{k-1} p$: the first $k-1$ times, you come back, and the $k^{\text{th}}$ time, you don't.

Misha Lavrov
  • 142,276