Calculating probability of reaching state in DTMC

Question

Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov Chain (DTMC) property: for each state the outflow transition weights are reals (or just rationals, if that makes a difference) in [0,1] which sum to 1, and the transition weights stay constant in time. So a finite state machine where the system moves through the states probabilistically, basically. For example:

Where $a_{0,1} + a_{0,2} = 1$, $a_{1,0} + a_{1,3} = 1$ etc.

Assume we start the system in the state where $x = 0$; what is the probability that the system reaches the state where $x = 3$, and what is the algorithm for determining that probability? From my small knowledge of probability, the algorithm requires summing of the probabilities of all finite paths that eventually reach $x = 3$; for example:

$P[F (x = 3)] = a_{0,1}\cdot a_{1,3} + a_{0,2}\cdot a_{2,3} + a_{0,1}\cdot a_{1,0} \cdot a_{0,1} \cdot a_{1,3} + \ldots$

Since it's possible for the system to loop indefinitely before reaching $x = 3$, this equation includes an infinite sum of infinite products and is beyond my ability to solve. How is something like this calculated?

Answer 1

The answer to your question very much depends on the values of the probabilities $a_{ij}$. If all are non-zero, then the DTMC forms one single strongly connected component and the probability of reaching $x=3$ is therefore $1$ (it is $1$ for any state in such a case in fact). This result comes from the Long-run theorem, which says that any finite DTMC eventually reaches a bottom SCC and visits all its states infinitely often.

Have a look at the lecture slides and notes of a course on probabilistic systems. Especially the third and fourth lecture.

In a general case, you would find with a graph analysis states that reach $x=3$ with probability $1$ denoted $S_1$ and those with probability $0$ denoted $S_0$. Then you have a set of states $S_?$ for which you don't yet know the probability. For them you construct a matrix $\mathbf{A}$ of transition probabilities (it will be a square matrix of size $|S_?|\times |S_?|$). Then you construct a vector $\mathbf{b}$ with one-step probability to reach $x=3$. A solution to $\mathbf{A}\cdot \mathbf{x} = \mathbf{b}$ gives you the probabilities for states in $S_?$.