  Hamiltonian Monte Carlo (HMC) is an efficient and effective means of sampling
posterior distributions on Euclidean space, which has been extended to
manifolds with boundary. However, some applications require an extension to
more general spaces. For example, phylogenetic (evolutionary) trees are defined
in terms of both a discrete graph and associated continuous parameters;
although one can represent these aspects using a single connected space, this
rather complex space is not suitable for existing HMC algorithms. In this
paper, we develop Probabilistic Path HMC (PPHMC) as a first step to sampling
distributions on spaces with intricate combinatorial structure. We define PPHMC
on orthant complexes, show that the resulting Markov chain is ergodic, and
provide a promising implementation for the case of phylogenetic trees in
open-source software. We also show that a surrogate function to ease the
transition across a boundary on which the log-posterior has discontinuous
derivatives can greatly improve efficiency.
