An MM Algorithm to Estimate Parameters in Continuous-Time Markov Chains

Prism and Storm are popular model checking tools that provide a number of powerful analysis techniques for Continuous-time Markov chains (CTMCs). The outcome of the analysis is strongly dependent on the parameter values used in the model which govern the timing and probability of events of the resulting CTMC. However, for some applications, parameter values have to be empirically estimated from partially-observable executions. In this work, we address the problem of estimating parameter values of CTMCs expressed as Prism models from a number of partially-observable executions which might possibly miss some dwell time measurements. The semantics of the model is expressed as a parametric CTMC (pCTMC), i.e., CTMC where transition rates are polynomial functions over a set of parameters. Then, building on a theory of algorithms known by the initials MM, for minorization–maximization, we present an iterative maximum likelihood estimation algorithm for pCTMCs. We present an experimental evaluation of the proposed technique on a number of CTMCs from the quantitative verification benchmark set. We conclude by illustrating the use of our technique in a case study: the analysis of the spread of COVID-19 in presence of lockdown countermeasures.