Sampling and approximation algorithms for Gibbs point processes

5^th March 2024, 13:00 6th Floor Conference Room 605, EEE
Dr. Andreas Göbel
Hasso Plattner Institute

Abstract

Gibbs point processes are probability distributions over continuous spaces, that describe random spatial events. In statistical physics they are used to model gases, fluids, or crystals, while in other fields they are used to model e.g. the growth of trees in a forest, the distribution of stars in the universe, or the location of cities on a map. The main computational tasks related to such a model are sampling from the point process and computing its partition function, which is the normalising constant of its distribution. In this talk we will discuss algorithmic approaches, developed over series of articles, that yield polynomial-time algorithms for (approximately) sampling from such point processes and for obtaining a randomised approximation of their partition functions, as well as quasi-polynomial deterministic algorithms for approximating their partition functions. Our view point is that of obtaining rigorous asymptotic running time guarantees for the broadest parameter-range possible, in terms of the fugacity $\lambda \in \mathbb{R}_{\ge 0}$ and a repulsive symmetric pair potential $\phi$ on a bounded measurable region $\mathbb{V}$ of a complete separable metric space, equipped with a locally finite reference volume measure $\nu$. We will focus on an algorithmic approach based on mapping repulsive Gibbs point processes to hard-core models on a natural family of geometric random graphs. We also give an overview of other approaches that have appeared in the literature.