Lifted TASEP: A Solvable Paradigm for Speeding up Many-Particle Markov Chains

Abstract

Virtually all Markov-chain Monte Carlo algorithms used for sampling a given distribution are reversible, and they satisfy the detailed-balance condition. For local chains, this leads to a slow, diffusive exploration of sample space. Significant speedups can be achieved through nonreversible algorithms with the given distribution as a targeted steady state. However, nonreversible algorithms for sampling are difficult to set up and to analyze, and exact speedup results for interacting many-particle systems are very rare. Here, we introduce the “lifted” totally asymmetric simple exclusion process (TASEP) as an exactly solvable paradigm for nonreversible many-particle Markov chains. It samples the same hard-sphere distribution as the Metropolis algorithm for symmetrically diffusing hard-core particles on a one-dimensional lattice. We solve the lifted TASEP by an unusual kind of coordinate Bethe ansatz and show that it exhibits polynomial (in particle number) speedups in the relaxation time for the asymptotic approach of the steady state, as well as the nonasymptotic mixing time, compared to both Metropolis and Kardar-Parisi-Zhang-based dynamics. The lifted TASEP is the reduction onto the one-dimensional lattice of the successful hard-sphere event-chain Monte Carlo algorithm, and we discuss that it can likewise be generalized to soft interaction potentials.