[Back]

L. Cardelli, R. Grosu, K.G. Larsen, M. Tribastone, M. Tschaikowski, A. Vandin:
"Lumpability for Uncertain Continuous-Time Markov Chains";
Talk: Proc. of QEST'21: the International Conference on Quantitative Evaluation of SysTems, Paris, France; 2021-08-23 - 2021-08-27; in: "Proc. of Quest'21, the 18th International Conference on Quantitative Evaluation of Systems", Springer, LNCS, (2021), 391 - 409.

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

Die Annahme der perfekten Kenntnis der Ratenparameter in zeitkontinuierlichen Markov-Ketten (CTMCs) wird untergraben, wenn sie mit der Realität konfrontiert werden, wo sie aufgrund mangelnder Informationen oder aufgrund von Messrauschen unsicher sein können. In dieser Arbeit betrachten wir unsichere CTMCs, bei denen angenommen wird, dass die Raten nicht-deterministisch mit der Zeit aus begrenzten kontinuierlichen Intervallen variieren. Dies führt zu einer Semantik, die jeden Zustand mit der erreichbaren Menge seiner Wahrscheinlichkeit unter allen möglichen Entscheidungen der unsicheren Raten assoziiert. Wir entwickeln einen Begriff der Klumpfähigkeit, der eine Partition von Zuständen identifiziert, bei der jeder Block die erreichbare Menge der Summe seiner Wahrscheinlichkeiten beibehält, und heben damit im Wesentlichen die bekannte gewöhnliche Klumpfähigkeit der CTMC auf die ungewisse Situation an. Wir setzen diese Analogie mit zwei weiteren Beiträgen fort: eine logische Charakterisierung der unsicheren CTMC-Klumpbarkeit in Form einer kontinuierlichen stochastischen Logik und ein Algorithmus mit polynomialer Zeit und Raum für die Minimierung von unsicheren CTMCs durch Partitionsverfeinerung, der den CTMC-Klumpbarkeitsalgorithmus als inneren Schritt verwendet. Als Fallstudie zeigen wir, dass die Minimierungen in einer beträchtlichen Anzahl von CTMC-Modellen, über die in der Literatur berichtet wird, robust sind in Bezug auf Unsicherheiten um ihre ursprünglichen, festen Ratenwerte

Lumpability, uncertainty, markov chains

http://dx.doi.org/10.1007/978-3-030-85172-9_21