A spectral independence view on hard spheres via block dynamics

DOI10.1137/21M143697XMaRDI QIDQ5043635zbMATH OpenFDO

Authors Tobias Friedrich, Andreas Göbel, Martin S. Krejca, Marcus Pappik

Publication date 6 October 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainpartition functionapproximate countingGibbs distributionGlauber dynamicshard-sphere modelspectral independence

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Approximation algorithms (68W25) Mathematical modeling or simulation for problems pertaining to statistical mechanics (82-10)

Abstract: The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in $d$ dimensions. Up to a fugacity of $lambda<exte/2^d$, the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.

Recommendations

• Correlation decay for hard spheres via Markov chains
• Algorithms and Computation
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• On the hardness of sampling independent sets beyond the tree threshold

Cites work

• scientific article; zbMATH DE number 1188967 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• scientific article; zbMATH DE number 7204480 (Why is no real title available?)
• Algorithms and Computation
• Combinatorial criteria for uniqueness of Gibbs measures
• Computing the independence polynomial: from the tree threshold down to the roots
• Correlation decay for hard spheres via Markov chains
• Correlation decay up to uniqueness in spin systems
• Counting independent sets up to the tree threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Disagreement percolation for the hard-sphere model
• Equation of state calculations by fast computing machines
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Improved analysis of higher order random walks and applications
• Inapproximability of the independent set polynomial in the complex plane
• MCMC sampling colourings and independent sets of \(G(n, d/n)\) near uniqueness threshold
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On Counting Independent Sets in Sparse Graphs
• On the hard sphere model and sphere packings in high dimensions
• On the hardness of sampling independent sets beyond the tree threshold
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Perfect simulation of the hard disks model by partial rejection sampling
• Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes
• Random sampling for the monomer-dimer model on a lattice.
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Sampling random colorings of sparse random graphs
• Self-avoiding walks and trees in spread-out lattices
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Spatial mixing and nonlocal Markov chains
• Spatial mixing and the connective constant: optimal bounds
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Strong spatial mixing for repulsive point processes
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• The analyticity region of the hard sphere gas. Improved bounds
• Theory of simple liquids. With applications to soft matter

Cited in

(5)

• Algorithms for hard-constraint point processes via discretization
• Algorithms and Computation
• Quasipolynomial-time algorithms for Gibbs point processes
• Polymer dynamics via cliques: new conditions for approximations
• Correlation decay for hard spheres via Markov chains

This page was built for publication: A spectral independence view on hard spheres via block dynamics

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