Source-linked AI summary
Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps
Manon Michel, Sebastian C. Kapfer, Werner Krauth
TL;DR
The paper extends hard-sphere event-chain Monte Carlo to particle systems with arbitrary pair potentials. It combines a factorized Metropolis filter with infinitesimal moves in a rejection-free event-driven algorithm, which performs better than conventional Metropolis Monte Carlo as system size grows and enables direct pressure and stress-tensor computation without extra computation.
Problem
The paper addresses extending hard-sphere event-chain Monte Carlo to particle systems with arbitrary pair-potential interactions.
Source: §I · p. 1, CONCLUSION · p. 7Method
A factorized Metropolis filter and infinitesimal moves form a rejection-free lifted event-chain algorithm implemented with an event-based BKL approach.
Source: §I · p. 1, CONCLUSION · p. 8Results
The generalized algorithm is faster than conventional Metropolis Monte Carlo, with the performance gap increasing with system size.
Source: §V · p. 6, CONCLUSION · p. 8Takeaways & Limitations
Its continuum of equilibrium samples permits direct pressure and stress-tensor computation in the NVT ensemble without additional computation.
Source: §I · p. 1, CONCLUSION · p. 8
Abstract
from arXiv · showhide
In this article, we present an event-driven algorithm that generalizes the recent hard-sphere event-chain Monte Carlo method without introducing discretizations in time or in space. A factorization of the Metropolis filter and the concept of infinitesimal Monte Carlo moves are used to design a rejection-free Markov-chain Monte Carlo algorithm for particle systems with arbitrary pairwise interactions. The algorithm breaks detailed balance, but satisfies maximal global balance and performs better than the classic, local Metropolis algorithm in large systems. The new algorithm generates a continuum of samples of the stationary probability density. This allows us to compute the pressure and stress tensor as a byproduct of the simulation without any additional computations.
I. INTRODUCTION
The paper brings lifted Markov chains and non-local Monte Carlo ideas to continuum particle systems, where lifted chains had not yet been applied. It introduces a factorized Metropolis filter and combines it with infinitesimal moves to construct a rejection-free event-chain algorithm.
I. INTRODUCTION
- Earlier lifted Markov chains had been applied to spin models [23,24], but not to continuum systems.The introduction places this gap alongside progress in non-local cluster moves and persistent algorithms.Source: §I · p. 1
- A factorized Metropolis filter for N-particle pair interactions, combined with infinitesimal moves, yields a rejection-free event-chain algorithm.The algorithm breaks detailed balance while satisfying maximal global balance.Source: §I · p. 1
- The event-driven algorithm produces a continuum of equilibrium samples and permits pressure and stress-tensor computation in the NVT ensemble without extra computation.For hard spheres it reduces to the hard-sphere event-chain algorithm; for general pair interactions, pairwise collisions replace hard-sphere collisions.Source: §I · p. 1
II. BALANCE CONDITIONS, FACTORIZED METROPOLIS FILTER
Global balance requires equal total probability flow into and out of each configuration, while detailed balance imposes the stronger pairwise flow symmetry. The paper introduces a factorized Metropolis filter that retains detailed balance but separates pair contributions, a property used to construct rejection-free lifted algorithms.
II. BALANCE CONDITIONS, FACTORIZED METROPOLIS FILTER
- Global balance equates total flow into and out of each configuration; detailed balance additionally equates flows between every pair of configurations.The Metropolis filter enforces detailed balance by making the flow symmetric between configurations.Source: §II · pp. 1–2
- Maximal global balance makes flow unidirectional between configurations and avoids rejected-move self-loops.In the particle systems considered, probability returns nonlocally through periodic boundaries.Source: §II · p. 2
- The factorized Metropolis filter retains detailed balance but expresses acceptance as a product of independent pair-interaction terms.Unlike the conventional filter, it differs for general interactions when N > 2.Source: §II · p. 2
- About 50% higher rejection rates occur with the factorized filter in detailed-balance Monte Carlo for soft spheres with n = 12, ρ = 0.8–1.2, and step size 0.1 particle diameters.The factorization's independent pair terms are the basis for deriving rejection-free lifted MCMC for general N-particle systems.Source: §II · p. 2
III. LIFTING: 1D SYSTEMS AND TWO PARTICLES IN A BOX
Lifting augments configurations with a direction-like variable that determines the next move, with lifting moves used to maintain flow balance when a proposed particle move is rejected. The one-dimensional hard-wall example maps to constrained two-particle motion in a periodic box.
III. LIFTING: 1D SYSTEMS AND TWO PARTICLES IN A BOX
- A lifting variable selects the next move, and lifting transitions take effect when the proposed particle move is rejected.The lifted configurations retain the original configuration weights; the lifted algorithm is rejection-free although physical-variable rejections remain.Source: §III · p. 3
- With uniform stationary probabilities and hard walls, the lifted walk visits all sites in O(L) steps, versus O(L^2) for Metropolis.At either boundary, the lifting flow equals the full incoming flow and reverses the particle's direction.Source: §III · p. 3
- The one-dimensional hard-wall walk corresponds to two hard spheres constrained to move along one direction in a periodic box.Resampling the moving sphere and direction restores ergodicity for the unconstrained two-sphere problem; move sequences between resampling are event chains.Source: §III · p. 3, Figure 2 · p. 3
IV. INFINITESIMAL MOVES AND EVENT-CHAIN ALGORITHM FOR INTERACTING MANYPARTICLE SYSTEMS
The factorized Metropolis filter turns infinitesimal moves into a rejection-free, maximal-global-balance event-chain algorithm for arbitrary pair potentials. An event-driven implementation finds lifting events directly, without fine time or space discretization.
IV. INFINITESIMAL MOVES AND EVENT-CHAIN ALGORITHM FOR INTERACTING MANYPARTICLE SYSTEMS
- For hard spheres, multiple overlaps can violate global balance at finite steps; as |∆| →0, a unique collision partner inherits the lifting variable.The infinitesimal algorithm is implemented by finding the next lifting event and advancing to contact, not by fine discretization.Source: §IV · pp. 3–4, Figure 3 · p. 4
- The factorized filter assigns pairwise energy-increase terms as lifting probabilities, yielding rejection-free moves with maximal global balance.For infinitesimal displacements, the rejection probability is a sum of pair terms, which need not sum to the total energy increase.Source: §IV · p. 4
- For arbitrary pair potentials, the algorithm treats each moving-particle interaction independently and selects the earliest lifting event among N −1 partners.The event displacement is found from a sampled admissible energy increase; if no solution exists, that pair generates no lifting event.Source: §IV · pp. 4–5
- Each chain advances by infinitesimal moves until its displacement reaches ℓ, then resamples the lifting variables.A chain may instead terminate with a small constant probability per infinitesimal move, producing exponentially distributed ℓ.Source: §IV · p. 5
- For monotonic soft-sphere potentials, lifting occurs only on the rising part; splitting attractive and repulsive terms simplifies implementation but can increase event rates.For Lennard-Jones interactions, the decomposition yields attractive and repulsive soft-sphere terms, reducing the mean free path at most by half.Source: §IV · p. 5
V. SPEEDUP WITH RESPECT TO METROPOLIS MONTE CARLO
In CPU-time comparisons, ECMC mixes a few times quicker than MMC in small systems, and its speedup increases with system size. For very large systems, MMC does not reach a stationary |Ψ6| distribution within the allotted simulation time, so τ6 was not determined.
V. SPEEDUP WITH RESPECT TO METROPOLIS MONTE CARLO
- The study estimates mixing using τ6 of the global orientational order parameter Ψ6, assuming it represents mixing time near the freezing point.The selected densities are ρσ2 = 1 for n = 12 and ρσ2 ≈0.89 for n = 1024.Source: §V · p. 5
- In small systems, ECMC mixes a few times quicker than MMC in CPU time.Both algorithms were tuned to their optimal parameters.Source: §V · p. 5
- ECMC speedup over MMC increases with system size, while the very-large-system MMC |Ψ6| distribution remains nonstationary and τ6 is not determined.The comparison uses τ6 of Ψ6 in comparable CPU-time units; the figure describes soft-disk systems at β = 1.Source: Figure 5 · p. 6, §V · p. 6
VI. DIRECT PRESSURE COMPUTATION
ECMC pressure estimates from excess displacement agree with the conventional virial approach without additional computation. The section derives pressure and stress estimators from virtual volume changes and lifting events.
VI. DIRECT PRESSURE COMPUTATION
- For hard spheres, direct pressure averaging is unavailable because the potential is singular, while virial estimation can require poorly sampled near-contact structure or extra force calculations.The excess-displacement estimator requires no extra computation and is particularly more efficient than the virial approach for steep potentials.Source: §VI · pp. 6–7
- Lifting-event rates relate directly to pressure and provide an elementary derivation for soft particles independent of the virial theorem; the result also applies to hard particles.The hard-particle connection can be derived using arguments relating pressure to the stochastic geometry of admissible configurations.Source: §VI · p. 6
- Removing a randomly located infinitesimal strip relates virtual volume changes to pressure, separating ideal-gas particle loss from non-ideal contributions of compressed bonds.For hard spheres, the non-ideal contribution arises from overlaps; for soft interactions, the successful-removal and overlap cases become indistinct.Source: §VI · pp. 6–7, Figure 6 · p. 6
- Summing lifting events over an event chain yields a pressure estimator from the chain's initial and final positions; for isotropic systems, only their displacement is needed.In the ideal gas there are no lifting moves, and the estimator reduces to ideal-gas pressure.Source: §VI · p. 7
- ECMC excess-displacement pressures agree with conventional virial results for repulsive soft spheres, hard spheres, and Lennard-Jones interactions.The comparison reports standard errors from 10 independent simulations for each case.Source: §VI · p. 7, Table I · p. 7
- For anisotropic systems, longitudinal and transverse rifts yield the full pressure, while the stress tensor is averaged from dyadic products of interparticle distances at collisions.The pressure derivation is supplemented with transverse rifts aligned with the event-chain direction.Source: §VI · p. 7
CONCLUSION
The paper generalizes event-chain Monte Carlo to arbitrary pair potentials using infinitesimal moves and a factorized Metropolis filter. The resulting algorithm is faster than conventional Metropolis Monte Carlo, with a performance gap that grows with system size.
CONCLUSION
- The event-chain Monte Carlo algorithm is generalized from hard spheres to arbitrary pair potentials, including Lennard-Jones liquids and soft disks.The algorithm is based on lifting and achieves maximal global balance using a factorized Metropolis filter applied to infinitesimal moves.Source: CONCLUSION · pp. 7–8
- The algorithm is faster than conventional Metropolis Monte Carlo, and its performance gap increases with system size.Infinitesimal moves are implemented efficiently with an event-based BKL approach.Source: CONCLUSION · p. 8
- Continuum samples of the equilibrium distribution allow pressure and stress-tensor computation directly from the simulation without additional computation.These quantities are derived in the NVT ensemble.Source: CONCLUSION · p. 8
- Infinitesimal moves enable lifted Markov chains for interacting particles by defining the next event uniquely while satisfying global balance.The original hard-sphere event-chain and the hybrid Monte Carlo algorithm of Peters and de With are also revealed as lifting algorithms when subdivided into infinitesimal moves.Source: CONCLUSION · p. 8
- Cooperative displacement of particle clusters improves mixing in large, strongly correlated systems, and the algorithm can be parallelized.The authors expect extensions to complex fluids with internal degrees of freedom, path-integral Monte Carlo, and other sampling problems.Source: CONCLUSION · p. 8