Seminar Details:

LANS Informal Seminar
"Improved diffusion Monte Carlo for quantum Monte Carlo, rare event simulation, data assimilation, and more"

DATE: August 29, 2013

TIME: 15:00:00 - 16:00:00
SPEAKER: Jonathan Weare, Assistant Professor, Department of Mathematics, The University of Chicago
LOCATION: Building 240, 1404-1405, Argonne National Laboratory

Description:
Diffusion Monte Carlo (DMC) is a workhorse of stochastic computing. It was invented forty years ago as the central component in a Monte Carlo technique for estimating various characteristics of quantum mechanical systems. Since then it has been used in applied in a huge number of fields, often as a central component in sequential Monte Carlo techniques (e.g. the particle filter). DMC computes averages of some underlying stochastic dynamics weighted by a functional of the path of the process. The weight functional could represent the potential term in a Feynman-Kac representation of a partial differential equation (as in quantum Monte Carlo) or it could represent the likelihood of a sequence of noisy observations of the underlying system (as in particle filtering). DMC alternates between an evolution step in which a collection of samples of the underlying system are evolved for some short time interval, and a branching step in which, according to the weight functional, some samples are copied and some samples are eliminated. Unfortunately for certain choices of the weight functional DMC fails to have a meaningful limit as one decreases the evolution time interval between branching steps. We propose a modification of the standard DMC algorithm. The new algorithm has a lower variance per workload, regardless of the regime considered. In particular, it makes it feasible to use DMC in situations where the ``naive'' generalization of the standard algorithm would be impractical, due to an exponential explosion of its variance. We numerically demonstrate the effectiveness of the new algorithm on a standard rare event simulation problem (probability of an unlikely transition in a Lennard-Jones cluster), as well as a high-frequency data assimilation problem. We then provide a detailed heuristic explanation of why, in the case of rare event simulation, the new algorithm is expected to converge to a limiting process as the underlying stepsize goes to 0. This is shown rigorously in the simplest possible situation of a random walk, biased by a linear potential. The resulting limiting object, which we call the ``Brownian fan'', is a very natural new mathematical object of independent interest.


 

Please send questions or suggestions to Krishna: snarayan at mcs.anl.gov.