# Fundamentals of Partial Rejection Sampling

arXiv: https://arxiv.org/abs/2106.07744 · HTML: https://mlsanity.com/paper/2106.07744/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2021.

## Built on by (most cited first, 3 of 3)

- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Learning Markov Random Fields for Combinatorial Structures via Sampling through Lov'asz Local Lemma](https://mlsanity.com/paper/2212.00296/) (2022)
- [Bypassing orthogonalization in the quantum DPP sampler](https://mlsanity.com/paper/2503.05906/) (2025)

## Abstract (arXiv)

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.