Stratification of Markov processes for rare event simulation

Jonathan Weare, University of Chicago
November 16th, 2016 at 3:30PM–4:30PM in 891 Evans Hall [Map]

I will discuss a Monte Carlo approach to computing statistical averages that is 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. It is a close relative of the classical stratified sampling approach that has long been a cornerstone of experimental design in statistics. 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. For this scheme we have developed error bounds that reveal that the existing understanding of umbrella sampling is incomplete and potentially misleading. We demonstrate that the improvement from umbrella sampling over direct simulation can be dramatic in certain regimes. 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. I will also briefly outline a “trajectory stratification’’ technique based on the nonequilibrium umbrella sampling method, that extends the stratified sampling philosophy to the calculation of dynamic averages with respect a given Markov process. The scheme is capable of computing very general averages and offers a natural way to parallelize in both time and space.