Finding the probability of a multi-state transition in a finite state machine

Question

I'm struggling to understand how to compute the probability of $q_{0} \rightarrow q_{3}$.

From my understanding, given that the transition from $q_{1}$ back to $q_{0}$ did not exist, the probability of reaching $q_{3}$ from $q_{0}$ would be $0.5 * 0.35$.

However, in the provided state diagram, we have a state transition from $q_{1} \rightarrow q_{0}$; in theory, this could occur an infinite amount of times before ever reaching $q_{3}$ - how do we incorporate this into our probability calculation?

Answer 1

The successful paths are of the form $q_0 \rightarrow (q_1 \rightarrow q_0)^n \rightarrow q_1 \rightarrow q_3$ with $n \geqslant 0$. The corresponding probability is $$ 0.5 \times \Bigl(\sum_{n \geqslant 0} (0.45 \times 0.5)^n \Bigr) \times 0.35 = 0.5 \times \Bigl(\frac{1}{ 1 - (0.45 \times 0.5)} \Bigr) \times 0.35 = \frac{0.5 \times 0.35}{0.775} = 0.22580645161\cdots $$

Answer 2

I'm not familiar with this exact kind of calculation, but I believe this procedure makes sense:

If we get to $q_3$, we have to pass through $q_1$ some nonzero number of times, let's call this number $n$ and the event of getting to $q_3$ passing $q_1 n$ times is $A_n$.

$n$ clearly can't take on more than one value for a single path, so we have disjoint spanning events. So, we can use the law of total probability to add up the probabilities for each value of $n$, which should give us a convergent infinite sum.

To begin with, if $n = 0$ it's pretty clear to see that the probability of getting to $q_3$ is simply $(0.5)(0.35) = 0.175$. Then, for any other value of $n$, starting from $q_0$ we have to run the loop once and then take the path with one fewer loop. This gives the recurrence relation $P(A_n) = 0.225P(A_{n-1})$. From here it should be clear that $P(A_n) = 0.175(0.225^n)$.

Now all we have to do is add up all of the probabilities: $P(A) = \Sigma_{n=0}^{\infty}0.175(0.225^n) = \frac{0.175}{1-0.225} = \frac{7}{31} = 0.2258$.

Hope this helps!