TITLE: Large deviations and accelerated Monte Carlo methods

ABSTRACT:

Monte Carlo methods have emerged as a set of indispensable tools in the applied sciences and engineering. In situations where the underlying stochastic model is too complex for analytical calculations to be tractable they offer a convenient way to obtain numerical approximations. However, the problem of rare-event sampling can often be a hindrance to the use such methods. In order to overcome this problem one must use some type of accelerated Monte Carlo method, in which a control mechanism is used to guide the particles in the simulation into the relevant parts of the state space. Earlier results in the area have shown that intuition can be misleading in the design of such controls and a proper theoretical analysis of the simulation method of choice is often needed.

The aim of this talk is to discuss the connection between Monte Carlo methods, and the rare-event sampling problem, and large deviations. Large deviation theory is the branch of probability theory that deals with rare events. In addition to providing estimates to the probabilities of such events, the theory also gives insight into how the events will occur. This is precisely the kind of insight needed to develop efficient Monte Carlo methods. After a brief overview of these two topics I will focus on the method known as importance sampling and how one can analyze and design efficient algorithms by means of large deviation theory. In particular, I will discuss connections to Hamilton-Jacobi equations and a recent results of ours on representations of solutions to such PDE’s and its applications to rare-event simulation.