Perfect simulation of the Hard Disks Model by Partial Rejection Sampling

Abstract

We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in $O(\log n)$ rounds, and total time $O(n)$, where $n$ is the expected number of disks. The method extends easily to the hard spheres model in $d>2$ dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.

Minor revisions. This version is accepted for publication in Annales de l'Institut Henri Poincaré D

References in corpus (5)

• The sphere packing problem in dimension 24
• The sphere packing problem in dimension 8
• On the hard sphere model and sphere packings in high dimensions
• Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics
• A note on partial rejection sampling for the hard disks model in the plane

Cited by in corpus (5)

• Strong spatial mixing for repulsive point processes
• Perfect sampling from spatial mixing
• Fundamentals of Partial Rejection Sampling
• A note on partial rejection sampling for the hard disks model in the plane
• Dynamic Sampling from Graphical Models