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

  • 2
    $\begingroup$ seems like it should be complete for a randomized version of $L$. $\endgroup$ – Artem Kaznatcheev Jan 26 '12 at 17:58
  • $\begingroup$ mixing time of chain can be exponential.. e.g. random walk on certain directed graphs. $\endgroup$ – singhsumit Jan 26 '12 at 19:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Joe Jan 30 '12 at 20:17
  • $\begingroup$ @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$. $\endgroup$ – Michael Ummels Feb 1 '12 at 14:30
  • $\begingroup$ @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. $\endgroup$ – Joe Feb 3 '12 at 23:31

Your Answer

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

Browse other questions tagged or ask your own question.