  Many problems of practical interest rely on Continuous-time Markov
chains~(CTMCs) defined over combinatorial state spaces, rendering the
computation of transition probabilities, and hence probabilistic inference,
difficult or impossible with existing methods. For problems with countably
infinite states, where classical methods such as matrix exponentiation are not
applicable, the main alternative has been particle Markov chain Monte Carlo
methods imputing both the holding times and sequences of visited states. We
propose a particle-based Monte Carlo approach where the holding times are
marginalized analytically. We demonstrate that in a range of realistic
inferential setups, our scheme dramatically reduces the variance of the Monte
Carlo approximation and yields more accurate parameter posterior approximations
given a fixed computational budget. These experiments are performed on both
synthetic and real datasets, drawing from two important examples of CTMCs
having combinatorial state spaces: string-valued mutation models in
phylogenetics and nucleic acid folding pathways.
