Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Guo, Heng; Jerrum, Mark http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-90739
URL:

;

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

pdf-format:


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
Seminar: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI