Document Open Access Logo

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

Authors Heng Guo , Mark Jerrum

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.69.pdf
  • Filesize: 0.48 MB
  • 10 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Hard disks model
  • Sampling
  • Markov chains

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Heng Guo and Mark Jerrum. Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 69:1-69:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.69

Author Details

Heng Guo
  • School of Informatics, University of Edinburgh, Informatics Forum, Edinburgh, EH8 9AB, United Kingdom.
Mark Jerrum
  • School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London, E1 4NS, United Kingdom.

Funding

  • Jerrum, Mark: The work described here was supported by the EPSRC research grant EP/N004221/1 "Algorithms that Count".

References

  1. Henry Cohn. A conceptual breakthrough in sphere packing. Notices Amer. Math. Soc., 64(2):102-115, 2017. Google Scholar
  2. Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska. The sphere packing problem in dimension 24. Ann. of Math. (2), 185(3):1017-1033, 2017. Google Scholar
  3. Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the Lovasz local lemma. In STOC, pages 342-355, 2017. Google Scholar
  4. Thomas C. Hales. A proof of the Kepler conjecture. Ann. of Math. (2), 162(3):1065-1185, 2005. Google Scholar
  5. Thomas P. Hayes and Cristopher Moore. Lower bounds on the critical density in the hard disk model via optimized metrics. CoRR, abs/1407.1930, 2014. Google Scholar
  6. Matthew Jenssen, Felix Joos, and Will Perkins. On the hard sphere model and sphere packings in high dimensions. ArXiv, abs/1707.00476, 2017. Google Scholar
  7. Ravi Kannan, Michael W. Mahoney, and Ravi Montenegro. Rapid mixing of several Markov chains for a hard-core model. In ISAAC, pages 663-675, 2003. Google Scholar
  8. Wilfrid S. Kendall. Perfect simulation for the area-interaction point process. In Probability towards 2000 (New York, 1995), volume 128 of Lect. Notes Stat., pages 218-234. Springer, New York, 1998. Google Scholar
  9. Wilfrid S. Kendall and Jesper Møller. Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. Appl. Probab., 32(3):844–-865, 2000. Google Scholar
  10. Torgny Lindvall. On Strassen’s theorem on stochastic domination. Electron. Comm. Probab., 4:51-59, 1999. Google Scholar
  11. Hartmut Löwen. Fun with hard spheres. In Klaus R. Mecke and Dietrich Stoyan, editors, Statistical Physics and Spatial Statistics, pages 295-331, 2000. Google Scholar
  12. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. J. Chem. Phys., 21(6):1087-1092, 1953. Google Scholar
  13. S. B. Moka, S. Juneja, and M. R. H. Mandjes. Perfect sampling for Gibbs processes with a focus on hard-sphere models. ArXiv, abs/1705.00142, 2017. Google Scholar
  14. Will Perkins. Birthday inequalities, repulsion, and hard spheres. Proc. Amer. Math. Soc., 144(6):2635-2649, 2016. Google Scholar
  15. Chris Preston. Spatial birth-and-death processes (with discussion). Bull. Inst. Internat. Statist., 46(2):371-391, 405-408 (1975), 1975. Google Scholar
  16. V. Strassen. The existence of probability measures with given marginals. Ann. Math. Statist., 36:423-439, 1965. Google Scholar
  17. David J. Strauss. A model for clustering. Biometrika, 62(2):467-475, 1975. Google Scholar
  18. Maryna S. Viazovska. The sphere packing problem in dimension 8. Ann. of Math. (2), 185(3):991-1015, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact