License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.69
URN: urn:nbn:de:0030-drops-90739
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9073/
Guo, Heng ;
Jerrum, Mark
Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling
Abstract
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O(log n) rounds, where n is the expected number of disks. The method extends easily to the hard spheres model in d>2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.
BibTeX - Entry
@InProceedings{guo_et_al:LIPIcs:2018:9073,
author = {Heng Guo and Mark Jerrum},
title = {{Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {69:1--69:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9073},
URN = {urn:nbn:de:0030-drops-90739},
doi = {10.4230/LIPIcs.ICALP.2018.69},
annote = {Keywords: Hard disks model, Sampling, Markov chains}
}
|
Keywords: |
|
Hard disks model, Sampling, Markov chains |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
