A spectral independence view on hard spheres via block dynamics

DOI10.1137/21M143697XzbMATH Open1498.60302arXiv2102.07443MaRDI QIDQ5043635FDOQ5043635

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

Publication date: 6 October 2022

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

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.

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

Recommendations

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

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)

Cites Work

• Equation of State Calculations by Fast Computing Machines
• On the hardness of sampling independent sets beyond the tree threshold
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Correlation Decay up to Uniqueness in Spin Systems
• The analyticity region of the hard sphere gas. Improved bounds
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• On Counting Independent Sets in Sparse Graphs
• Theory of simple liquids. With applications to soft matter
• Title not available (Why is that?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Title not available (Why is that?)
• Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes
• Combinatorial criteria for uniqueness of Gibbs measures
• Random sampling for the monomer-dimer model on a lattice.
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Title not available (Why is that?)
• Algorithms and Computation
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold
• Spatial mixing and the connective constant: optimal bounds
• ON THE HARD SPHERE MODEL AND SPHERE PACKINGS IN HIGH DIMENSIONS
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Sampling Random Colorings of Sparse Random Graphs
• Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
• Title not available (Why is that?)
• Self-avoiding walks and trees in spread-out lattices
• Title not available (Why is that?)
• Swendsen‐Wang dynamics for general graphs in the tree uniqueness region
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Spatial mixing and nonlocal Markov chains
• Strong spatial mixing for repulsive point processes
• Correlation decay for hard spheres via Markov chains
• Disagreement percolation for the hard-sphere model
• Inapproximability of the independent set polynomial in the complex plane
• Improved analysis of higher order random walks and applications

Cited In (3)

• Polymer dynamics via cliques: new conditions for approximations
• Quasipolynomial-time algorithms for Gibbs point processes
• Algorithms for hard-constraint point processes via discretization

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)