Lumpability for Uncertain Continuous-Time Markov Chains

Luca Cardelli; Radu Grosu; Kim G. Larsen; Mirco Tribastone; Max Tschaikowski; Andrea Vandin

doi:10.1007/978-3-030-85172-9_21

Lumpability for Uncertain Continuous-Time Markov Chains

Luca Cardelli, Radu Grosu, Kim G. Larsen, Mirco Tribastone, Max Tschaikowski^*, Andrea Vandin

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

307 Downloads (Orbit)

Abstract

The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. In this paper we consider uncertain CTMCs, where rates are assumed to vary non-deterministically with time from bounded continuous intervals. This leads to a semantics which associates each state with the reachable set of its probability under all possible choices of the uncertain rates. We develop a notion of lumpability which identifies a partition of states where each block preserves the reachable set of the sum of its probabilities, essentially lifting the well-known CTMC ordinary lumpability to the uncertain setting. We proceed with this analogy with two further contributions: a logical characterization of uncertain CTMC lumping in terms of continuous stochastic logic; and a polynomial time and space algorithm for the minimization of uncertain CTMCs by partition refinement, using the CTMC lumping algorithm as an inner step. As a case study, we show that the minimizations in a substantial number of CTMC models reported in the literature are robust with respect to uncertainties around their original, fixed, rate values.

Original language	English
Title of host publication	Quantitative Evaluation of Systems
Editors	Alessandro Abate, Andrea Marin
Publisher	Springer
Publication date	2021
Pages	391-409
ISBN (Print)	9783030851712
DOIs	https://doi.org/10.1007/978-3-030-85172-9_21
Publication status	Published - 2021
Event	18^th International Conference on Quantitative Evaluation of Systems - Virtual, Online Duration: 23 Aug 2021 → 27 Aug 2021 https://www.qest.org/qest2021/

Conference

Conference	18^th International Conference on Quantitative Evaluation of Systems
City	Virtual, Online
Period	23/08/2021 → 27/08/2021
Internet address	https://www.qest.org/qest2021/

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12846 LNCS
ISSN	0302-9743

Bibliographical note

Funding Information:
Acknowledgement. Luca Cardelli is supported by a Royal Society Research Professorship. The work has been partially supported by the ERC Advanced Grant LASSO, the Villum Investigator Grant S4OS, the EU-Ecsel project iDev40, the FFG project Adex, the PRIN project SEDUCE, no. 2017TWRCNB, the FWF project COCO no. M-2393-N32, the Poul Due Jensen Foundation grant no. 883901, and by the DFF RP1 project REDUCTO no. 9040-00224B.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-85172-9_21

FulltextAccepted author manuscript, 478 KB

OpenUrl availability

Full text

Cite this

Cardelli, Luca ; Grosu, Radu ; Larsen, Kim G. et al. / Lumpability for Uncertain Continuous-Time Markov Chains. Quantitative Evaluation of Systems. editor / Alessandro Abate ; Andrea Marin. Springer, 2021. pp. 391-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12846 LNCS).

@inproceedings{6659f52098cd40bc92bf9ead9c30c5cb,

title = "Lumpability for Uncertain Continuous-Time Markov Chains",

abstract = "The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. In this paper we consider uncertain CTMCs, where rates are assumed to vary non-deterministically with time from bounded continuous intervals. This leads to a semantics which associates each state with the reachable set of its probability under all possible choices of the uncertain rates. We develop a notion of lumpability which identifies a partition of states where each block preserves the reachable set of the sum of its probabilities, essentially lifting the well-known CTMC ordinary lumpability to the uncertain setting. We proceed with this analogy with two further contributions: a logical characterization of uncertain CTMC lumping in terms of continuous stochastic logic; and a polynomial time and space algorithm for the minimization of uncertain CTMCs by partition refinement, using the CTMC lumping algorithm as an inner step. As a case study, we show that the minimizations in a substantial number of CTMC models reported in the literature are robust with respect to uncertainties around their original, fixed, rate values.",

author = "Luca Cardelli and Radu Grosu and Larsen, \{Kim G.\} and Mirco Tribastone and Max Tschaikowski and Andrea Vandin",

note = "Funding Information: Acknowledgement. Luca Cardelli is supported by a Royal Society Research Professorship. The work has been partially supported by the ERC Advanced Grant LASSO, the Villum Investigator Grant S4OS, the EU-Ecsel project iDev40, the FFG project Adex, the PRIN project SEDUCE, no. 2017TWRCNB, the FWF project COCO no. M-2393-N32, the Poul Due Jensen Foundation grant no. 883901, and by the DFF RP1 project REDUCTO no. 9040-00224B. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 18<sup>th</sup> International Conference on Quantitative Evaluation of Systems, QEST 2021 ; Conference date: 23-08-2021 Through 27-08-2021",

year = "2021",

doi = "10.1007/978-3-030-85172-9\_21",

language = "English",

isbn = "9783030851712",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "391--409",

editor = "Alessandro Abate and Andrea Marin",

booktitle = "Quantitative Evaluation of Systems",

url = "https://www.qest.org/qest2021/",

}

Cardelli, L, Grosu, R, Larsen, KG, Tribastone, M, Tschaikowski, M & Vandin, A 2021, Lumpability for Uncertain Continuous-Time Markov Chains. in A Abate & A Marin (eds), Quantitative Evaluation of Systems. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12846 LNCS, pp. 391-409, 18^th International Conference on Quantitative Evaluation of Systems, Virtual, Online, 23/08/2021. https://doi.org/10.1007/978-3-030-85172-9_21

Lumpability for Uncertain Continuous-Time Markov Chains. / Cardelli, Luca; Grosu, Radu; Larsen, Kim G. et al.
Quantitative Evaluation of Systems. ed. / Alessandro Abate; Andrea Marin. Springer, 2021. p. 391-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12846 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Lumpability for Uncertain Continuous-Time Markov Chains

AU - Cardelli, Luca

AU - Grosu, Radu

AU - Larsen, Kim G.

AU - Tribastone, Mirco

AU - Tschaikowski, Max

AU - Vandin, Andrea

N1 - Funding Information: Acknowledgement. Luca Cardelli is supported by a Royal Society Research Professorship. The work has been partially supported by the ERC Advanced Grant LASSO, the Villum Investigator Grant S4OS, the EU-Ecsel project iDev40, the FFG project Adex, the PRIN project SEDUCE, no. 2017TWRCNB, the FWF project COCO no. M-2393-N32, the Poul Due Jensen Foundation grant no. 883901, and by the DFF RP1 project REDUCTO no. 9040-00224B. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. In this paper we consider uncertain CTMCs, where rates are assumed to vary non-deterministically with time from bounded continuous intervals. This leads to a semantics which associates each state with the reachable set of its probability under all possible choices of the uncertain rates. We develop a notion of lumpability which identifies a partition of states where each block preserves the reachable set of the sum of its probabilities, essentially lifting the well-known CTMC ordinary lumpability to the uncertain setting. We proceed with this analogy with two further contributions: a logical characterization of uncertain CTMC lumping in terms of continuous stochastic logic; and a polynomial time and space algorithm for the minimization of uncertain CTMCs by partition refinement, using the CTMC lumping algorithm as an inner step. As a case study, we show that the minimizations in a substantial number of CTMC models reported in the literature are robust with respect to uncertainties around their original, fixed, rate values.

AB - The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. In this paper we consider uncertain CTMCs, where rates are assumed to vary non-deterministically with time from bounded continuous intervals. This leads to a semantics which associates each state with the reachable set of its probability under all possible choices of the uncertain rates. We develop a notion of lumpability which identifies a partition of states where each block preserves the reachable set of the sum of its probabilities, essentially lifting the well-known CTMC ordinary lumpability to the uncertain setting. We proceed with this analogy with two further contributions: a logical characterization of uncertain CTMC lumping in terms of continuous stochastic logic; and a polynomial time and space algorithm for the minimization of uncertain CTMCs by partition refinement, using the CTMC lumping algorithm as an inner step. As a case study, we show that the minimizations in a substantial number of CTMC models reported in the literature are robust with respect to uncertainties around their original, fixed, rate values.

U2 - 10.1007/978-3-030-85172-9_21

DO - 10.1007/978-3-030-85172-9_21

M3 - Article in proceedings

AN - SCOPUS:85115157731

SN - 9783030851712

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 391

EP - 409

BT - Quantitative Evaluation of Systems

A2 - Abate, Alessandro

A2 - Marin, Andrea

PB - Springer

T2 - 18<sup>th</sup> International Conference on Quantitative Evaluation of Systems

Y2 - 23 August 2021 through 27 August 2021

ER -

Cardelli L, Grosu R, Larsen KG, Tribastone M, Tschaikowski M, Vandin A. Lumpability for Uncertain Continuous-Time Markov Chains. In Abate A, Marin A, editors, Quantitative Evaluation of Systems. Springer. 2021. p. 391-409. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12846 LNCS). doi: 10.1007/978-3-030-85172-9_21

Lumpability for Uncertain Continuous-Time Markov Chains

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this