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.
| Type: | Proceedings paper |
|---|---|
| Title: | Computing quantiles in Markov chains with multi-dimensional costs |
| Event: | 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
| ISBN-13: | 9781509030187 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1109/LICS.2017.8005090 |
| Publisher version: | https://doi.org/10.1109/LICS.2017.8005090 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Markov processes, Probabilistic logic, Computational modeling, Approximation algorithms, Probability distribution, Numerical models, Complexity theory |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10088918 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
