  Bayesian inference for Continuous-Time Markov Chains (CTMCs) on countably
infinite spaces is notoriously difficult because evaluating the likelihood
exactly is intractable. One way to address this challenge is to first build a
non-negative and unbiased estimate of the likelihood -- involving the matrix
exponential of finite truncations of the true rate matrix -- and then to use
the estimates in a pseudo-marginal inference method. In this work, we show that
we can dramatically increase the efficiency of this approach by avoiding the
computation of exact matrix exponentials. In particular, we develop a general
methodology for constructing an unbiased, non-negative estimate of the
likelihood using doubly-monotone matrix exponential approximations. We further
develop a novel approximation in this family -- the skeletoid -- as well as
theory regarding its approximation error and how that relates to the variance
of the estimates used in pseudo-marginal inference. Experimental results show
that our approach yields more efficient posterior inference for a wide variety
of CTMCs.
