{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:02:33Z","timestamp":1787508153093,"version":"build-2736575974"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2018,3,20]]},"abstract":"<jats:p>We consider the problem of generating perfect samples from a Gibbs point process, a spatial process that is absolutely continuous w.r.t. a Poisson point process. Examples include area-interaction processes, hard-sphere models and Strauss processes. Traditionally, this is addressed using coupling from the past (CFTP) based methods. We consider acceptance-rejection methods that, unlike the common CFTP methods, do not have the impatient-user bias. Our key contribution is a novel importance sampling based acceptance- rejection methodology for generating perfect samples from Gibbs point processes. We focus on a simpler setting of hard-sphere models in a d-dimensional hypercube that we analyze in an asymptotic regime where the number of spheres generated increases to infinity while the sphere radius decreases to zero at varying rates.<\/jats:p>","DOI":"10.1145\/3199524.3199536","type":"journal-article","created":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T11:17:48Z","timestamp":1521717468000},"page":"69-75","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Analysis of Perfect Sampling Methods for Hard-sphere Models"],"prefix":"10.1145","volume":"45","author":[{"given":"S. B.","family":"Moka","sequence":"first","affiliation":[{"name":"UQ, Brisbane"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Juneja","sequence":"additional","affiliation":[{"name":"TIFR, Mumbai"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. R. H.","family":"Mandjes","sequence":"additional","affiliation":[{"name":"University of Amsterdam"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,3,20]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Stochastic Modelling and Applied Probability","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-69033-9","volume-title":"Stochastic simulation: algorithms and analysis","author":"Asmussen S.","year":"2007","unstructured":"Asmussen , S. , and Glynn , P. W . Stochastic simulation: algorithms and analysis , vol. 57 of Stochastic Modelling and Applied Probability . Springer , New York , 2007 . Asmussen, S., and Glynn, P. W. Stochastic simulation: algorithms and analysis, vol. 57 of Stochastic Modelling and Applied Probability. Springer, New York, 2007."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1497879"},{"key":"e_1_2_1_3_1","volume-title":"A spatial Markov Queueing Process and its Applications to Wireless Loss Systems. Research report","author":"Baccelli F.","year":"2007","unstructured":"Baccelli , F. , Blaszczyszyn , B. , and Karray , M. K . A spatial Markov Queueing Process and its Applications to Wireless Loss Systems. Research report , 2007 Baccelli, F., Blaszczyszyn, B., and Karray, M. K. A spatial Markov Queueing Process and its Applications to Wireless Loss Systems. Research report, 2007"},{"key":"e_1_2_1_4_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2009","unstructured":"Cormen , T. H. , Leiserson , C. E. , Rivest , R. L. , and Stein , C . Introduction to algorithms , third ed. MIT Press , Cambridge, MA , 2009 . Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms, third ed. MIT Press, Cambridge, MA, 2009."},{"key":"e_1_2_1_5_1","series-title":"Stochastic Modelling and Applied Probability","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03311-7","volume-title":"Large deviations techniques and applications","author":"Dembo A.","year":"2010","unstructured":"Dembo , A. , and Zeitouni , O . Large deviations techniques and applications , vol. 38 of Stochastic Modelling and Applied Probability . Springer-Verlag , Berlin , 2010 . Corrected reprint of the second (1998) edition. Dembo, A., and Zeitouni, O. Large deviations techniques and applications, vol. 38 of Stochastic Modelling and Applied Probability. Springer-Verlag, Berlin, 2010. Corrected reprint of the second (1998) edition."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Nonuniform random variate generation","author":"Devroye L.","year":"1986","unstructured":"Devroye , L. Nonuniform random variate generation . Springer-Verlag , New York , 1986 . Devroye, L. Nonuniform random variate generation. Springer-Verlag, New York, 1986."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(02)00180-1"},{"key":"e_1_2_1_8_1","first-page":"131","article-title":"An interruptible algorithm for perfect sampling via markov chains","volume":"8","author":"Fill J. A","unstructured":"Fill , J. A . An interruptible algorithm for perfect sampling via markov chains . Ann. Appl. Probab. 8 , 1 (02 1998), 131 - 162 . Fill, J. A. An interruptible algorithm for perfect sampling via markov chains. Ann. Appl. Probab. 8, 1 (02 1998), 131-162.","journal-title":"Ann. Appl. Probab."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4%3C290::AID-RSA6%3E3.0.CO;2-Q"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825238"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.3150\/10-BEJ350"},{"key":"e_1_2_1_12_1","volume-title":"Chapman & Hall\/CRC Monographs on Statistics & Applied Probability","author":"Huber M. L.","year":"2016","unstructured":"Huber , M. L. Perfect Simulation . Chapman & Hall\/CRC Monographs on Statistics & Applied Probability . CRC Press , 2016 . Huber, M. L. Perfect Simulation. Chapman & Hall\/CRC Monographs on Statistics & Applied Probability. CRC Press, 2016."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1377868538"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1013540247"},{"key":"e_1_2_1_15_1","volume-title":"Acceptance-rejection and Importance Sampling Methodologies for Perfect Sampling from Gibbs Point Processes. ArXiv:1705.00142 {math.PR} (Apr","author":"Moka S. B.","year":"2017","unstructured":"Moka , S. B. , Juneja , S. , and Mandjes , M. R. H . Acceptance-rejection and Importance Sampling Methodologies for Perfect Sampling from Gibbs Point Processes. ArXiv:1705.00142 {math.PR} (Apr . 2017 ). Moka, S. B., Juneja, S., and Mandjes, M. R. H. Acceptance-rejection and Importance Sampling Methodologies for Perfect Sampling from Gibbs Point Processes. ArXiv:1705.00142 {math.PR} (Apr. 2017)."},{"key":"e_1_2_1_16_1","volume-title":"Statistical Mechanics","author":"Pathria R.","year":"1972","unstructured":"Pathria , R. Statistical Mechanics . Elsevier Science , 1972 . Pathria, R. Statistical Mechanics. Elsevier Science, 1972."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-7757(99)00413-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.459318"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1029954267"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.50.955"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199524.3199536","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199524.3199536","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:07:17Z","timestamp":1750259237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199524.3199536"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,20]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3,20]]}},"alternative-id":["10.1145\/3199524.3199536"],"URL":"https:\/\/doi.org\/10.1145\/3199524.3199536","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2018,3,20]]},"assertion":[{"value":"2018-03-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}