Fundamentals of partial rejection sampling

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. Working within a unified framework allows a clean expression of the running time, and clarifies the scope for nondeterminism in its implementation.