Generating transition paths with Markov bridges

We present a method to sample Markov chain trajectories constrained to both initial and final condition, which we term Markov bridges. The trajectories are conditioned to end in a specific state at a given time. We derive the master equation for Markov bridges, which exhibits the original transition rates scaled by a time-dependent factor. Trajectories can then be generated using a refined version of the Gillespie algorithm. We demonstrate the validity of our method by applying it to the diffusion on the one-dimensional lattice, for which exact results are available. Next we apply our method to a more complex example, namely trajectories in the Müller-Brown potential. This allows us to generate transition paths which would otherwise be obtained at high computational cost with standard Kinetic Monte Carlo methods. Finally, we show how our method can be used to shed light on the dynamics of complex system by applying it to single-cell RNA data from the pancreas to investigate cell differentiation pathways