How do I find probability of leaf nodes in cyclic direct graph?

Question

So I have this graph:

where the initial state is $s_0$ and the only two terminal states are $s_2$ and $s_4$. The probability of the next state is given by the fraction on the arrows.

My task is to find the probability of reaching a terminal state (either $s_2$ or $s_4$) starting from $s_0$.

Empirically, I have found that $p(s_2) = 2/3$ and $p(s_4) = 1/3$.

I understand how to calculate the probability if there are no cycles (by simply tracing and multiplying the probabilities) or just one cycle (by tracing and using converging geometric series) but I don't understand how to calculate the probability if the cycles are intertwined (e.g. $s_1$ and $s_0$ create a cycle which is intertwined with the cycle $s_0, s_1, s_3$)

Any ideas would be very much appreciated!

Answer 1

Write $p,q,r$ for the probabilities of reaching S2 from S0, S1 and S3 respectively. Then we have:

• $p=q$ (since from S0 you always move to S1 and then have probability $q$)
• $q=1/3+p/3+r/3$ (since after one step from S1 you are equally likely to have probability $1$, $p$ or $r$)
• $r=p/2+0/2$ (similarly).

Now you can solve these simultaneous equations to get values for $p,q,r$.