Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - The Odds of Staying on Budget


Christoph Haase and Stefan Kiefer. The odds of staying on budget. Technical report,, 2015. Available at


Given Markov chains and Markov decision processes (MDPs) whose transitions are labelled with non-negative integer costs, we study the computational complexity of deciding whether the probability of paths whose accumulated cost satisfies a Boolean combination of inequalities exceeds a given threshold. For acyclic Markov chains, we show that this problem is PP-complete, whereas it is hard for the PosSLP problem and in PSPACE for general Markov chains. Moreover, for acyclic and general MDPs, we prove PSPACE- and EXP-completeness, respectively. Our results have direct implications on the complexity of computing reward quantiles in succinctly represented stochastic systems.

Suggested BibTeX entry:

    author = {Christoph Haase and Stefan Kiefer},
    institution = {},
    note = {Available at},
    title = {The Odds of Staying on Budget},
    year = {2015}

See ...
Conference version