Fundamentals of Partial Rejection Sampling
arXiv:2106.07744 · doi:10.1214/24-PS29
Abstract
Partial Rejection Sampling is an algorithmic approach to obtaining a perfect sample from a specified distribution. The objects to be sampled are assumed to be represented by a number of random variables. In contrast to classical rejection sampling, in which all variables are resampled until a feasible solution is found, partial rejection sampling aims at greater efficiency by resampling only a subset of variables that `go wrong'. Partial rejection sampling is closely related to Moser and Tardos' algorithmic version of the Lovász Local Lemma, but with the additional requirement that a specified output distribution should be met. This article provides a largely self-contained account of the basic form of the algorithm and its analysis.
arXiv commentSome expansion/clarification, especially in Section 4, two extra figures
References in corpus (9)
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Perfect Sampling Using Bounding Chains
- Random curves on surfaces induced from the Laplacian determinant
- A polynomial-time approximation algorithm for all-terminal network reliability
- An Improvement of the Lovász Local Lemma via Cluster Expansion
- Approximately counting bases of bicircular matroids
- Perfect simulation of the Hard Disks Model by Partial Rejection Sampling
- Perfect sampling from spatial mixing