2021/07/19 by Tobias Friedrich, Friedrich, Tobias, Andreas Göbel +7
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2107.08848
openalex publication_date 2021/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study algorithmic applications of a natural discretization for the hard-sphere model and the Widom-Rowlinson model in a region \mathbbV⊂ℝd. These models are used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles follow a Poisson point process with a type specific activity parameter (fugacity). The Gibbs distribution is characterized by the mixture of these point processes conditioned that no two particles are closer than a type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. We give sufficient conditions that the partition function of a discrete hard-core model on a geometric graph based on a point set X ⊂ \mathbbV closely approximates those of such continuous models. Previously, this was only shown for the hard-sphere model on cubic regions \mathbbV=[0, ℓ)d when X is exponential in the volume of the region ν(\mathbbV), limiting algorithmic applications. In the same setting, our refined analysis only requires a quadratic number of points, which we argue to be tight. We use our improved discretization results to approximate the partition functions of the hard-sphere model and the Widom-Rowlinson efficiently in ν(\mathbbV). For the hard-sphere model, we obtain the first quasi-polynomial deterministic approximation algorithm for the entire fugacity regime for which, so far, only randomized approximations are known. Furthermore, we simplify a recently introduced fully polynomial randomized approximation algorithm. Similarly, we obtain the best known deterministic and randomized approximation bounds for the Widom-Rowlinson model. Moreover, we obtain approximate sampling algorithms for the respective spin systems within the same fugacity regimes.