Clarendon Laboratory, Department of Physics, University of Oxford, Parks Road, Oxford, OX1 3PU
Professor Werner Krauth, Ecole Normale Superieure Paris
Joy Blanchard at tpadmin@physics.ox.ac.uk
Monte Carlo sampling beyond the diffusive regime
Abstract: Markov-chain Monte Carlo permeates all fields of science, from physics to statistics and to the social disciplines. Reversible Markov chains, the great majority of Monte Carlo methods, map the sampling of probability distributions onto the simulation of fictitious physical systems in thermal equilibrium. In physics, thermal equilibrium is characterized by time-reversal invariance and the detailed-balance condition. It thus comes as no surprise that reversible Markov chains, such as the famous Metropolis and heat-bath algorithms, all satisfy detailed balance. In physics, again, thermal equilibrium is characterized by diffusive, local, motion of particles.This slowness translates to the slow mixing and relaxation dynamics of local reversible Markov chains, and it affects most Markov chains used in practice.
In this talk, I confront diametrically opposite strategies to overcome the slow diffusive motion of local, reversible MCMC methods. One is Hamiltonian Monte Carlo, a non-local yet reversible Markov chain that models the physical dynamics, and the other is event-chain Monte Carlo, a class of lifted Markov chains, which are local yet non-reversible. In a simple one-dimensional continuum model of interacting particles, I show that event-chain Monte Carlo reaches better scaling of relaxation times than the physical "real-life" dynamics of Hamiltonian Monte Carlo. I will connect this finding to recent work on the lifted TASEP (lifted totally asymmetric simple exclusion model), which is exactly solvable through the Bethe ansatz, and which allows for a mathematical analysis based on true self-avoiding random walks. I will finally discuss applications to real-world problems, where event-chain Monte Carlo allows one to sample the Boltzmann distribution exp(-beta U) without evaluating the energy U.