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.

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.