Efficient continuous-time Markov chain estimation

Many problems of practical interest rely on Continuous-time Markov chains (CTMCs) defined over combinatorial state spaces, ren-dering the computation of transition prob-abilities, and hence probabilistic inference, difficult or impossible with existing meth-ods. For problems with countably infinite states, where classical methods such as ma-trix 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 approxi-mations given a fixed computational budget. These experiments are performed on both synthetic and real datasets, drawing from two important examples of CTMCs having com-binatorial state spaces: string-valued muta-tion models in phylogenetics and nucleic acid folding pathways. 1