6
$\begingroup$

A discrete-time Markov chain (DTMC) is a tuple $M=(S,s_{init},P)$ where $S$ is a finite set of states, $s_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability matrix.

For a subset $S'\subseteq S$ with $s_{init},t\in S'$ we define the induced sub-DTMC $M_{S'}=(S',s_{init},P')$ with $P'(s,s')=P(s,s')$ for all $s,s'\in S'$. If the sum of the out-going probabilities of a state $s\in S'$ is less than 1, a deadlock state is entered with probability $1-\sum_{s'\in S'}P(s,s')$ such that $t$ cannot be reached anymore.

Assume we are given a DTMC $M=(S,s_{init},P)$ and a target state $t\in S$ such that the probability to finally reach $t$ from $s_{init}$ is larger than a given bound $\lambda$. We are interested in subsets $S'\subseteq S$ with $s_{init},t\in S'$ such that the probability of reaching $t$ from $s_{init}$ in $M_{S'}$ is still larger than $\lambda$.

Question: What is the complexity of deciding whether there is such a $S'$ containing at most $k$ states (for a given $k$)?

We suppose that this problem is NP-complete (obviously it is in NP: guess an appropriate $S'$ and compute the reachability probabilities to check if the bound $\lambda$ is exceeded; this can be done by solving a linear equation system). However, we have not found a reduction to show the NP-hardness. Maybe someone can help ...


For Markov decision processes, which feature non-deterministic choices in addition to the probabilistic choices of DTMCs, the same problem has been proven to be NP-complete, see

Chadha, Viswanathan - A counterexample-guided abstraction-refinement framework for Markov decision processes, ACM Trans. Comput. Log. 12(1), 2010 http://dl.acm.org/citation.cfm?doid=1838552.1838553

The same holds also for DTMCs and PCTL properties, if nested formulae are allowed. However, for pure reachability I was not able to find a proof for NP-hardness.

$\endgroup$
  • $\begingroup$ I do not know how you interpret M_{S′} as a Markov chain, because the probabilities of transition from s to s′ do not sum to 1 when summed over s′∈S′. Do you renormalize the probabilities, or do you consider everything outside S′ as a blackhole? $\endgroup$ – Tsuyoshi Ito Aug 31 '12 at 16:41
  • $\begingroup$ If the out-going probabilities of a state $s$ do not sum up to 1, you run into a deadlock with probability $1-\sum_{s'\in S'}P(s,s')$. $\endgroup$ – Roffle Aug 31 '12 at 16:59
  • $\begingroup$ Please edit your question. $\endgroup$ – Tsuyoshi Ito Aug 31 '12 at 17:00
  • 1
    $\begingroup$ And "deadlocking" is equivalent to moving along a self-loop of the current vertex so that in the next time step, there is the possibility of leaving this vertex or is "deadlocking" equivalent to moving to a new sink vertex who's only outgoing edge is a self-loop and is taken with probability 1? $\endgroup$ – Tyson Williams Aug 31 '12 at 21:34
  • 1
    $\begingroup$ No, deadlocking is equivalent to moving to a absorbing state from which the target state $t$ cannot be reached. $\endgroup$ – Roffle Sep 1 '12 at 6:54

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.