Differentiated uniformization: a new method for inferring Markov chains on combinatorial state spaces including stochastic epidemic models

Computational Statistics, vol. 39, pp. 3643–3663

Abstract

Abstract We consider continuous-time Markov chains that describe the stochastic evolution of a dynamical system by a transition-rate matrix Q which depends on a parameter $$\theta $$ θ . Computing the probability distribution over states at time t requires the matrix exponential $$\exp \,\left( tQ\right) \,$$ exp t Q , and inferring $$\theta $$ θ from data requires its derivative $$\partial \exp \,\left( tQ\right) \,/\partial \theta $$ ∂ exp t Q / ∂ θ . Both are challenging to compute when the state space and hence the size of Q is huge. This can happen when the state space consists of all combinations of the values of several interacting discrete variables. Often it is even impossible to store Q. However, when Q can be written as a sum of tensor products, computing $$\exp \,\left( tQ\right) \,$$ exp t Q becomes feasible by the uniformization method, which does not require explicit storage of Q. Here we provide an analogous algorithm for computing $$\partial \exp \,\left( tQ\right) \,/\partial \theta $$ ∂ exp t Q / ∂ θ , the differentiated uniformization method. We demonstrate our algorithm for the stochastic SIR model of epidemic spread, for which we show that Q can be written as a sum of tensor products. We estimate monthly infection and recovery rates during the first wave of the COVID-19 pandemic in Austria and quantify their uncertainty in a full Bayesian analysis. Implementation and data are available at https://github.com/spang-lab/TenSIR .

Authors 8

1. Kevin Rupp

   University of Regensburg

   Affiliation as printed

   Department of Statistical Bioinformatics, University of Regensburg, 93040, Regensburg, Germany

2. Rudolf Schill corresponding

   University of Regensburg

   Affiliation as printed

   Department of Statistical Bioinformatics, University of Regensburg, 93040, Regensburg, Germany

3. Jonas Sueskind

   University of Regensburg

   Affiliation as printed

   Department of Statistical Bioinformatics, University of Regensburg, 93040, Regensburg, Germany

4. Peter Georg

   University of Regensburg

   Affiliation as printed

   Department of Physics, University of Regensburg, 93040, Regensburg, Germany

5. Maren Klever Aachen Institut für Geometrie und Praktische Mathematik

   RWTH Aachen University

   Affiliation as printed

   Institut für Geometrie und Praktische Mathematik, RWTH Aachen University, 52062, Aachen, Germany

6. Lars Grasedyck Aachen Institut für Geometrie und Praktische Mathematik

   RWTH Aachen University

   Affiliation as printed

   Institut für Geometrie und Praktische Mathematik, RWTH Aachen University, 52062, Aachen, Germany

7. Tilo Wettig

   University of Regensburg

   Affiliation as printed

   Department of Physics, University of Regensburg, 93040, Regensburg, Germany

8. Rainer Spang corresponding

   University of Regensburg

   Affiliation as printed

   Department of Statistical Bioinformatics, University of Regensburg, 93040, Regensburg, Germany