# 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?

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