3
$\begingroup$

I'm stucked in this markov chain problem. I need to know the probability of reaching the absorbing state "C" right after hitting the state "B" and starting at the state "A". The matrix transition is:

     A     B      C
    0.79  0.2    0.01   A
    0.7   0.28   0.02   B
     0     0      1     C

Thank you very much in advance.

$\endgroup$
4
  • $\begingroup$ Hint: Possible ways of doing this: $$ABC, ABABC, ABABABC, \dots$$You can work out these probabilities and sum them, giving a geometric sum $\endgroup$
    – John Doe
    Apr 10, 2018 at 11:47
  • $\begingroup$ Yes, I was thinking that, but I can't come up with a way of compiling every possible sequence ... $\endgroup$
    – Yogesh
    Apr 10, 2018 at 11:49
  • 1
    $\begingroup$ But, it isn't that simple as going from A to B everytime right? it can do "AAABBBABABAAC" and there is a lot of probabilities inside that path, right? $\endgroup$
    – Yogesh
    Apr 10, 2018 at 11:58
  • $\begingroup$ Ahh yes you're right, my comment above misses a lot of cases. See my alternative method in my answer. $\endgroup$
    – John Doe
    Apr 10, 2018 at 11:59

1 Answer 1

3
$\begingroup$

Denote the probability of reaching $C$ starting from the point $i$ and going through $B$ by $p_i$. Then we have the two equations $$p_A=0.2p_B+0.79p_A\\p_B=0.02+0.7p_A+0.28 p_B$$ Solve these to find $p_A$, which is what they ask for.


How did we get these equations?

The first equation says the way to reach your target, starting at $A$ is by either first going to $B$ then figuring out how to reach the target from there, or by going straight back to $A$, and figuring out how to reach the target from there.

The second equation says the way to reach your target starting at $B$ is by either going straight to $C$ (which is your target, so you're done), or by going to $A$ then figuring out how to get to your target from there, or by going to $B$ then figuring out how to get to your target from there.

This is a common method used for solving problems like this (Markov processes).

$\endgroup$
10
  • $\begingroup$ Thanks man! Can you elaborate a bit? or quote me any source about this kind of problems? I'm struggling to understand it $\endgroup$
    – Yogesh
    Apr 10, 2018 at 12:17
  • $\begingroup$ @Yogesh I elaborated on how we reached these equations. Do you have any other specific questions? Such as what you don't particularly understand? $\endgroup$
    – John Doe
    Apr 10, 2018 at 12:27
  • $\begingroup$ Oooh. Yeah!! I completely get it now man. Thank you so much. PS: I can't upvote your answer due to have less than 15 reputation, but feel upvoted! $\endgroup$
    – Yogesh
    Apr 10, 2018 at 12:38
  • 1
    $\begingroup$ @David with Markov chains we look at the probabilities as one-step processes, so stuff like $\Bbb P(X_1=x_1|X_0=x_0)$. So we're computing the probability of going to some state ($x_1$) given that we are already at some other state ($x_0$). In this question we were looking at the probability of going along some path which ends with a jump from B to C. $p_i$ is just this - the probability of reaching C by going through B, having started at $i$. If we set $i=A$, the first equation naturally follows, but has a $p_B$ term in it, so we need the second equation to solve the problem. Make more sense? $\endgroup$
    – John Doe
    May 8, 2020 at 10:21
  • 1
    $\begingroup$ @David So you could try to work that out given each starting state, then compute a weighted sum of these, with the weights signifying the probability of starting at each state (this is necessary). Explicitly, you would assume that you randomly start at one of states A,B,C with probabilities $q_A,q_B,q_C$ (e.g. $q_A=q_B=q_C=\frac13$). Denote $p_j(t)=P(X_t=i|X_0=j)$. Then the probability of being at state $i$ at some time $T$ is $P(X_T=i)=q_Ap_A(T)+q_Bp_B(T)+q_Bp_B(T)$. $\endgroup$
    – John Doe
    May 10, 2020 at 20:07

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.