Sparse hard-disk packings and local Markov chains

DOI10.1007/S10955-022-02908-4MaRDI QIDQ2131132zbMATH OpenOpenAlexFDO

Authors Philipp Höllmer, Nicolas Noirault, Botao Li, A. C. Maggs, Werner Krauth

Publication date 25 April 2022

Published in Journal of Statistical Physics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2109.13343

zbMATH Keywords

Böröczky packingsevent-chain Monte Carlohard-disk modelhard-disk packingsMarkov chainsmixing timesstability

Mathematics Subject Classification ID

Discrete geometry (52C99) Markov processes (60J99) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

Abstract: We propose locally stable sparse hard-disk packings, as introduced by B"or"oczky, as a model for the analysis and benchmarking of Markov-chain Monte Carlo (MCMC) algorithms. We first generate such packings in a square box with periodic boundary conditions and analyze their properties. We then study how local MCMC algorithms, namely the Metropolis algorithm and several versions of event-chain Monte Carlo (ECMC), escape from configurations that are obtained by slightly reducing all disk radii by a relaxation parameter. A scaling analysis is confirmed by simulation results. We obtain two classes of ECMC, one in which the escape time varies algebraically with the relaxation parameter (as for the local Metropolis algorithm) and another in which the escape time scales as the logarithm of the relaxation parameter. We discuss the connectivity of the hard-disk sample space, the ergodicity of local MCMC algorithms, as well as the meaning of packings in the context of the NPT ensemble. Our work is accompanied by open-source, arbitrary-precision software for B"or"oczky packings (in Python) and for straight, reflective, forward, and Newtonian ECMC (in Go).

Recommendations

• PDMP characterisation of event-chain Monte Carlo algorithms for particle systems
• Algorithms and Computation
• scientific article; zbMATH DE number 1283998
• Perfect simulation of the hard disks model by partial rejection sampling
• Perfect simulation of the hard disks model by partial rejection sampling

Cites work

• A linear programming algorithm to test for jamming in hard-sphere packings
• Algorithms and Computation
• Analysis of a nonreversible Markov chain sampler.
• Cluster algorithm for hard spheres and related systems
• Combinatorial geometry and its algorithmic applications. The Alcalá lectures
• Equation of state calculations by fast computing machines
• Forward Event-Chain Monte Carlo: Fast Sampling by Randomness Control in Irreversible Markov Chains
• Geometric analysis for the Metropolis algorithm on Lipschitz domains
• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 1332581 (Why is no real title available?)
• scientific article; zbMATH DE number 3213309 (Why is no real title available?)
• Lifting Markov chains to speed up mixing
• Min-type Morse theory for configuration spaces of hard spheres
• Sparse locally-jammed disk packings
• Statistical mechanics: Algorithms and computations. With CD-ROM.
• The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov Chain Monte Carlo Method
• Über einen geometrischen Satz

Cited in

(3)

• BigBoro
• PDMP characterisation of event-chain Monte Carlo algorithms for particle systems
• Molecular simulation from modern statistics

Describes a project that uses

Uses Software

• Python

This page was built for publication: Sparse hard-disk packings and local Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2131132)