Computing Quantiles in Markov Reward Models
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p ∈ ]0,1] and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far.
In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with nonnegative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in pseudo-polynomial time.
In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with nonnegative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in pseudo-polynomial time.
Details
Originalsprache | Englisch |
---|---|
Titel | Foundations of Software Science and Computation Structures |
Redakteure/-innen | Frank Pfenning |
Herausgeber (Verlag) | Springer, Berlin [u. a.] |
Seiten | 353-368 |
Seitenumfang | 16 |
ISBN (Print) | 978-3-642-37074-8 |
Publikationsstatus | Veröffentlicht - 2013 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Lecture Notes in Computer Science, Volume 7794 |
---|---|
ISSN | 0302-9743 |
Konferenz
Titel | 15th International Conference on Foundations of Software Science and Computational Structures |
---|---|
Untertitel | Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013 |
Kurztitel | FoSSaCS 2013 |
Veranstaltungsnummer | |
Dauer | 16 - 24 März 2013 |
Bekanntheitsgrad | Internationale Veranstaltung |
Ort | |
Stadt | Rom |
Land | Italien |
Externe IDs
Scopus | 84874426860 |
---|---|
ORCID | /0000-0002-5321-9343/work/142236750 |
Schlagworte
Schlagwörter
- quantiles, Markov Reward Models