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, and the other is event-chain Monte Carlo, a class oflifted 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 Hamiltonian Monte Carlo. I will connect this finding, on the one hand, to recent work on a related lattice model, the lifted TASEP (lifted totally asymmetric simple exclusion model), which is exactly solvable through the Bethe ansatz, and on the other hand to the “true” self-avoiding walk. 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.