Annales de l’Institut Henri Poincaré D


Full-Text PDF (539 KB) | List online-first AIHPD articles | AIHPD summary
Published online first: 2021-03-03
DOI: 10.4171/AIHPD/99

Perfect simulation of the hard disks model by partial rejection sampling

Heng Guo[1] and Mark Jerrum[2]

(1) University of Edinburgh, UK
(2) Queen Mary, University of London, UK

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.

Keywords: Hard disks model, exact sampling, rejection sampling

Guo Heng, Jerrum Mark: Perfect simulation of the hard disks model by partial rejection sampling. Ann. Inst. Henri Poincaré Comb. Phys. Interact. Electronically published on March 3, 2021. doi: 10.4171/AIHPD/99 (to appear in print)