Understanding umbrella sampling approaches to rare event simulation

Abstract:

I will discuss an ensemble sampling scheme based on a decomposition of the target average of interest into subproblems that are each individually easier to solve and can be solved in parallel. The most basic version of the scheme computes averages with respect to a given density and is a generalization of the Umbrella Sampling method for the calculation of free energies. We have developed a careful understanding of the accuracy of the scheme that is sufficiently detailed to explain the success of umbrella sampling in practice and to suggest improvements including adaptivity. For equilibrium versions of the scheme we have developed error bounds that reveal that the existing understanding of umbrella sampling is incomplete and leads to a number of erroneous conclusions about the scheme. Our bounds are motivated by new perturbation bounds for Markov Chains that we recently established and that are substantially more detailed than existing perturbation bounds for Markov chains. They demonstrate, for example, that equilibrium umbrella sampling is robust in the sense that in limits in which the straightforward approach to sampling from a density becomes exponentially expensive, the cost to achieve a fixed accuracy with umbrella sampling can increase only polynomially. I will also discuss extensions of the stratification philosophy to the calculation of dynamic averages with respect a given Markov process. The scheme is capable of computing very general dynamic averages and offers a natural way to parallelize in both time and space.