Publication Details

Adaptive formal approximations of Markov chains

ABATE Alessandro, ANDRIUSHCHENKO Roman, ČEŠKA Milan and KWIATKOWSKA Marta. Adaptive formal approximations of Markov chains. Performance Evaluation, vol. 148, no. 102207, 2021, pp. 1-23. ISSN 0166-5316. Available from: https://www.sciencedirect.com/science/article/pii/S0166531621000249
Czech title
Adaptivní aproximace Markovových řetězců
Type
journal article
Language
english
Authors
Abate Alessandro (UOx)
Andriushchenko Roman, Ing. (DITS FIT BUT)
Češka Milan, doc. RNDr., Ph.D. (DITS FIT BUT)
Kwiatkowska Marta (UOx)
URL
Keywords

Markov models, 
Probabilistic model checking, 
Approximation techniques, 
Adaptive aggregation

Abstract

We explore formal approximation techniques for Markov chains based on state-space reduction that aim at improving the scalability of the analysis, while providing formal bounds on the approximation error. We first present a comprehensive survey of existing state-reduction techniques based on clustering or truncation. Then, we extend existing frameworks for aggregation-based analysis of Markov chains by allowing them to handle chains with an arbitrary structure of the underlying state space - including continuous-time models - and improve upon existing bounds on the approximation error. Finally, we introduce a new hybrid scheme that utilises both aggregation and truncation of the state space and provides the best available approach for approximating continuous-time models. We conclude with a broad and detailed comparative evaluation of existing and new approximation techniques and investigate how different methods handle various Markov models. The results also show that the introduced hybrid scheme significantly outperforms existing approaches and provides a speedup of the analysis up to a factor of 30 with the corresponding approximation error bounded within 0.1%.

Published
2021
Pages
1-23
Journal
Performance Evaluation, vol. 148, no. 102207, ISSN 0166-5316
Publisher
Elsevier Science
DOI
UT WoS
000648542900002
EID Scopus
BibTeX
@ARTICLE{FITPUB12500,
   author = "Alessandro Abate and Roman Andriushchenko and Milan \v{C}e\v{s}ka and Marta Kwiatkowska",
   title = "Adaptive formal approximations of Markov chains",
   pages = "1--23",
   journal = "Performance Evaluation",
   volume = 148,
   number = 102207,
   year = 2021,
   ISSN = "0166-5316",
   doi = "10.1016/j.peva.2021.102207",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12500"
}
Back to top