# Complexity of reachability in Markov Chains

Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the probability of eventually reaching $F$ from $q_0$ greater than (or equal to) $\frac{1}{2}$?

• seems like it should be complete for a randomized version of $L$. – Artem Kaznatcheev Jan 26 '12 at 17:58
• mixing time of chain can be exponential.. e.g. random walk on certain directed graphs. – singhsumit Jan 26 '12 at 19:00
• If F includes all of the absorbing states in M, and at least one state in F is reachable from $q_0$, then you will eventually end up in F with probability 1. If there are some absorbing states not in F, or you bound how much time you have, then the question is more interesting. – Joe Jan 30 '12 at 20:17
• @Joe: Even if $F$ includes all absorbing states, there may be bottom SCCs with more than one state reachable from $q_0$. Then the probability of eventually reaching $F$ is $<1$. – Michael Ummels Feb 1 '12 at 14:30
• @MichaelUmmels good point. I guess you could think of that whole section as a meta-state, so that while any individual state within it is not absorbing, the meta state that encapsulates the whole subset of states is absorbing. – Joe Feb 3 '12 at 23:31