Fundamentals of Partial Rejection Sampling
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909317513347072 |
|---|---|
| author | Jerrum, Mark |
| author_facet | Jerrum, Mark |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_07744 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Fundamentals of Partial Rejection Sampling Jerrum, Mark Data Structures and Algorithms Discrete Mathematics Probability 68Q25 (Primary), 05A15, 60C05, 68R05, 68W20, 68W40 (Secondary) 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. |
| title | Fundamentals of Partial Rejection Sampling |
| topic | Data Structures and Algorithms Discrete Mathematics Probability 68Q25 (Primary), 05A15, 60C05, 68R05, 68W20, 68W40 (Secondary) |
| url | https://arxiv.org/abs/2106.07744 |