Haase, C; Kiefer, S; Lohrey, M; (2017) Computing quantiles in Markov chains with multi-dimensional costs. In: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE: Reykjavik, Iceland.

Preview

Text Haase_Kiefer+et+al,+Computing+quantiles+in+Markov+Chains+with+multi-dimensional+costs.pdf - Accepted Version Download (600kB) | Preview

Abstract

Probabilistic systems that accumulate quantities such as energy or cost are naturally modelled by cost chains, which are Markov chains whose transitions are labelled with a vector of numerical costs. Computing information on the probability distribution of the total accumulated cost is a fundamental problem in this model. In this paper, we study the so-called cost problem, which is to compute quantiles of the total cost, such as the median cost or the probability of large costs. While it is an open problem whether such probabilities are always computable or even rational, we present an algorithm that allows to approximate the probabilities with arbitrary precision. The algorithm is simple to state and implement, and exploits strong results from graph theory such as the so-called BEST theorem for efficiently computing the number of Eulerian circuits in a directed graph. Moreover, our algorithm enables us to show that a decision version of the cost problem lies in the counting hierarchy, a counting analogue to the polynomial-time hierarchy that contains the latter and is included in PSPACE. Finally, we demonstrate the applicability of our algorithm by evaluating it experimentally.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item