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

finite-state machineprobability

Example FSM
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?

Best Answer

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

Related Question