A Spectral Independence View on Hard Spheres via Block Dynamics - Département d'informatique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2022

A Spectral Independence View on Hard Spheres via Block Dynamics

Résumé

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 < e/2 d , the runtime of our algorithm is polynomial in the volume of the system. 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 block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.
Fichier principal
Vignette du fichier
clique_spectral_independence.pdf (880.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03904167 , version 1 (10-01-2023)

Identifiants

Citer

Tobias Friedrich, Andreas Göbel, Martin S. Krejca, Marcus Pappik. A Spectral Independence View on Hard Spheres via Block Dynamics. SIAM Journal on Discrete Mathematics, 2022, 36 (3), pp.2282-2322. ⟨10.1137/21M143697X⟩. ⟨hal-03904167⟩
24 Consultations
15 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More