Fundamentals of Partial Rejection Sampling

Publication date 14 June 2021

Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Analysis of algorithms (68W40)

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'asz 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.

This page was built for publication: Fundamentals of Partial Rejection Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370305)