Probability to visit a node exactly n times in a markov chain 
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?
 A: 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.
