# Calculating probability of reaching state in DTMC

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?

## 1 Answer

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

• Thanks for the course reference, a paper linked on the course page (Model-Checking Meets Probability: A Gentle Introduction by Joost-Pieter Katoen [pdf]) was especially helpful. Oct 14, 2019 at 17:14