Irreversible Local Markov Chains with Rapid Convergence towards Equilibrium

We study the continuous one-dimensional hard-sphere model and present irreversible local Markov chains that mix on faster time scales than the reversible heat bath or Metropolis algorithms. The mixing time scales appear to fall into two distinct universality classes, both faster than for reversible local Markov chains. The event-chain algorithm, the infinitesimal limit of one of these Markov chains, belongs to the class presenting the fastest decay. For the lattice-gas limit of the hard-sphere model, reversible local Markov chains correspond to the symmetric simple exclusion process (SEP) with periodic boundary conditions. The two universality classes for irreversible Markov chains are realized by the totally asymmetric SEP (TASEP), and by a faster variant (lifted TASEP) that we propose here. We discuss how our irreversible hard-sphere Markov chains generalize to arbitrary repulsive pair interactions and carry over to higher dimensions through the concept of lifted Markov chains and the recently introduced factorized Metropolis acceptance rule.

Figure 1

Mixing of local 1D Markov chains. (a) Relaxation of $\mathrm{Var}{u}_i$ from the compact initial state under heat bath dynamics ($x$ axis rescaled by $N^3$, $y$ axis by equilibrium value). (b) Rescaling of $x$ axis with an additional logarithm illustrates $O(N^3\log N)$ time scale. (c) Mixing times for the Markov chains discussed in this Letter. The step $ϵ$ is uniformly sampled from ($0;2.5{\ell }_{\mathrm{free}}$). For the event-chain algorithm, ${\tau }_{\mathrm{mix}}$ is measured in lifting moves.

Figure 2

Metropolis flow into configuration $a$ by moves of sphere $i$. For given $ϵ$, $[{\mathcal{A}}_i^{\pm }(ϵ),{\mathcal{R}}_i^{\mp }(ϵ)]\in \{[1,0],[0,1]\}$ as a move by $ϵ$ is either accepted or rejected. Flows here are integrated over the step distribution $p(ϵ)$. The relation $[{\mathcal{A}}_i^{+}(ϵ),{\mathcal{R}}_{i-1}^{+}(ϵ)]\in \{[1,0],[0,1]\}$ justifies the forward Metropolis algorithm.

Figure 3

Update rules for discrete models. (a) The TASEP advances a random sphere, if possible, and it mixes in $O(N^{5/2})$. (b) The lifted TASEP, without restarts, is deterministic. With restarts, it mixes in $O(N^2\log N)$.

Figure 4

Restarts in the lifted Metropolis algorithm. (a) Mixing time as a function of chain length $\lambda \sim N$: The $O(N^2\log N)$ time scale is preserved but mixing is fastest for $\lambda \simeq 0.9N$. (b) $O(N^{5/2})$ mixing for $\lambda \sim N^{1/4}$ [asymptotically equivalent to the (unlifted) forward Metropolis algorithm, $\lambda =1$, red triangles] and for $\lambda \sim N^2$ (asymptotically equivalent to lifted Metropolis without any restarts, $\lambda =\infty$, red bullets).