1
$\begingroup$

So I have this graph:

enter image description here

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!

$\endgroup$
1
  • $\begingroup$ Have you learnt Markov chain with absorbing state? $\endgroup$ – BGM May 9 '17 at 6:56
1
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.