Stratified MCMC Sampling of non-Reversible Dynamics

Abstract

The study of stratified sampling is of interest in systems which canbe solved accurately on small scales, or which depend heavily on rare transitions of particles from one subspace to another. We present a new form of stratified MCMC algorithm built with non-reversible stochastic dynamics in mind. The method has potential usefulness in that many systems of interest are non-reversible, and can also benefit from stratification at the same time. It may also be useful for sampling on complex manifolds, and hence manifold learning. Our method is a generalization of previous stratified or nested sampling schemes which extend QSD sampling schemes. It can also be viewed as a generalization of the exact milestoning method previously studied by D. Aristoff. The primary advantages of our new results over such previous studies are generalization to non-reversible processes, expressions for the convergence rate in terms of the process's behavior within each stratum and large scale behavior between strata, and less restrictive assumptions for convergence. We show that the algorithm has a unique fixed point which corresponds to the invariant measure of the process without stratification. We will show how the speeds of two versions of the new algorithm, one with an extra eigenvalue problem step and one without, relate to the mixing rate of a discrete process on the strata, and the mixing probability of the process being sampled within each stratum. The eigenvalue problem version also relates to local and global perturbation results of discrete Markov chains, such as those given by J. Weare. Finally, we will propose a way to relate the accuracy of finite approximations of a process using our stratified scheme to its expected exit times from each stratum and its approximation of the true process's generator, by means of a Poisson equation argument.