2
$\begingroup$

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:

Probabilistic state machine graph

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ahelwer Oct 14 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.