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

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 \) $\theta$ . Computing the probability distribution over states at time t requires the matrix exponential \(\exp \,\left( tQ\right) \,\) $exp\left(t,Q\right)$ , and inferring \(\theta \) $\theta$ from data requires its derivative \(\partial \exp \,\left( tQ\right) \,/\partial \theta \) $\partial exp\left(t,Q\right)/\partial \theta$ . 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\left(t,Q\right)$ 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 \) $\partial exp\left(t,Q\right)/\partial \theta$ , 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.