Fast stochastic sampling with irreversible, totally asymmetric, Markov chains

Werner Krauth
École Normale Supérieure

The Monte Carlo method is an outstanding computational tool in science. Since its origins, it has relied on the detailed-balance condition, i.e. on the concept of reversible Markov chains, to solve general computational problems under the conditions of thermodynamic equilibrium with zero probability flows.

In this talk, I discuss irreversible Markov chains that violate detailed balance, yet satisfy global balance. Equilibrium is reached as a steady state with non-vanishing probability flows. For one-dimensional particle models, we can show explicitly that these algorithms reach equilibrium on much faster time scales than the reversible algorithms. The generalization of irreversible Markov chains to higher dimensions relies on the replacement of the Metropolis acceptance criterion by a new consensus rule, the factorized Metropolis algorithm. The system energy is not computed, providing a fresh perspective for long-range interactions. Moves are infinitesimal and persistent, and employ the powerful lifting framework. The algorithms are free of rejections and totally asymmetric because, if a move a -> b is allowed, the move b -> a is prohibited.

As applications, I mention the 2-d melting problem for hard disks and general potentials, continuous spin models, plasmas with long-range interactions, and the connection with one-dimensional models, such as the totally asymmetric simple exclusion model (TASEP).

Presentation (PDF File)

Back to Long Programs