Differentiated uniformization: A new method for inferring Markov chains
  on combinatorial state spaces including stochastic epidemic models
  Motivation: 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(tQ)$, and
inferring $\theta$ from data requires its derivative
$\partial\exp\!(tQ)/\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(tQ)$ becomes
feasible by the uniformization method, which does not require explicit storage
of $Q$.
  Results: Here we provide an analogous algorithm for computing
$\partial\exp\!(tQ)/\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.
  Availability: Implementation and data are available at
https://github.com/spang-lab/TenSIR.
