<p>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}$?</p>

CC BY-SA 3.0
2012-01-26T17:58:49.040Z
seems like it should be complete for a randomized version of $L$.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-26T19:00:43.003Z
mixing time of chain can be exponential.. e.g. random walk on certain directed graphs.
singhsumit
CC BY-SA 3.0
2012-01-30T20:17:11.290Z
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
CC BY-SA 3.0
2012-02-01T14:30:54.347Z
@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
CC BY-SA 3.0
2012-02-03T23:31:18.130Z
@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
<cc.complexity-theory><time-complexity><markov-chains>
Complexity of reachability in Markov Chains
Michael Ummels
# Complexity of reachability in Markov Chains

(Asked by: username_0 on 2012-01-26)

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}$?

**Tags:** cc.complexity-theory, time-complexity, markov-chains
> **Comments:**
> **username_1**: seems like it should be complete for a randomized version of $L$.  
> **username_2**: mixing time of chain can be exponential.. e.g. random walk on certain directed graphs.  
> **username_3**: 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.  
> **username_0**: @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$.  
> **username_3**: @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.  

---

## 0 answers

