Alexander Erreygers

Computing Inferences for Large-Scale Continuous-Time Markov Chains by Combining Lumping with Imprecision

Alexander Erreygers & Jasper De Bock

In the proceedings of the 9th International Conference on Soft Methods in Probability and Statistics (SMPS 2018), pp. 78-86, Sep. 2018.

Winner of the International Journal of Approximate Reasoning Best Paper Award.

Abstract If the state space of a homogeneous continuous-time Markov chain is too large, making inferences - here limited to determining marginal or limit expectations - becomes computationally infeasible. Fortunately, the state space of such a chain is usually too detailed for the inferences we are interested in, in the sense that a less detailed - smaller - state space suffices to unambiguously formalise the inference. However, in general this so-called lumped state space inhibits computing exact inferences because the corresponding dynamics are unknown and/or intractable to obtain. We address this issue by considering an imprecise continuous-time Markov chain. In this way, we are able to provide guaranteed lower and upper bounds for the inferences of interest, without suffering from the curse of dimensionality.