DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Computing Quantiles in Markov Reward Models

Ummels, Michael and Baier, Christel (2013) Computing Quantiles in Markov Reward Models. In: Foundations of Software Science and Computation Structures, 7794, pp. 353-368. Springer. FOSSACS 2013, 18.-20. März 2013, Rom, Italien. ISBN 978 3 642 37074 8. ISSN 0302-9743.

[img] PDF (Vortragsfolien)

Official URL: http://dx.doi.org/10.1007/978-3-642-37075-5_23


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 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 non-negative 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 time polynomial in the size of the chain and the maximum reward.

Item URL in elib:https://elib.dlr.de/82743/
Document Type:Conference or Workshop Item (Speech)
Title:Computing Quantiles in Markov Reward Models
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Ummels, Michaelmichael.ummels (at) dlr.deUNSPECIFIED
Baier, ChristelTU DresdenUNSPECIFIED
Journal or Publication Title:Foundations of Software Science and Computation Structures
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:No
Page Range:pp. 353-368
EditorsEmailEditor's ORCID iD
Pfennig, FrankCarnegie Mellon UniversityUNSPECIFIED
Series Name:Lecture Notes in Computer Science
ISBN:978 3 642 37074 8
Keywords:Quantiles, Markov Decision Processes, Probabilistic Model Checking
Event Title:FOSSACS 2013
Event Location:Rom, Italien
Event Type:international Conference
Event Dates:18.-20. März 2013
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Transport
HGF - Program Themes:Traffic Management (old)
DLR - Research area:Transport
DLR - Program:V VM - Verkehrsmanagement
DLR - Research theme (Project):V - Project Next Generation Railway System II (old)
Location: Braunschweig
Institutes and Institutions:Institute of Transportation Systems > Railway System
Deposited By: Ummels, Michael
Deposited On:02 Jul 2013 10:39
Last Modified:31 Jul 2019 19:41

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.