Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-27T12:31:24.925Z Has data issue: false hasContentIssue false
  • English
  • Français

Rejection- and importance-sampling-based perfect simulation for Gibbs hard-sphere models

Part of: Algorithms - Computer Science Limit theorems Probabilistic methods, simulation and stochastic differential equations Stochastic processes

Published online by Cambridge University Press:  08 October 2021

Sarat Moka ,
Sandeep Juneja  and
Michel Mandjes
Sarat Moka*
Affiliation:
University of Queensland
Sandeep Juneja*
Affiliation:
Tata Institute of Fundamental Research
Michel Mandjes*
Affiliation:
University of Amsterdam
*
*Postal address: School of Mathematics and Physics, Coopers Road, St Lucia, QLD, Australia 4072. Email: s.babumoka@uq.edu.au
**Postal address: Homi Bhabha Road, Colaba, Mumbai, India 400005. Email: juneja@tifr.res.in
***Postal address: Korteweg-de Vries Institute for Mathematics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, The Netherlands. Email: m.r.h.mandjes@uva.nl
Get access Rights & Permissions [Opens in a new window]

Abstract

Coupling-from-the-past (CFTP) methods have been used to generate perfect samples from finite Gibbs hard-sphere models, an important class of spatial point processes consisting of a set of spheres with the centers on a bounded region that are distributed as a homogeneous Poisson point process (PPP) conditioned so that spheres do not overlap with each other. We propose an alternative importance-sampling-based rejection methodology for the perfect sampling of these models. We analyze the asymptotic expected running time complexity of the proposed method when the intensity of the reference PPP increases to infinity while the (expected) sphere radius decreases to zero at varying rates. We further compare the performance of the proposed method analytically and numerically with that of a naive rejection algorithm and of popular dominated CFTP algorithms. Our analysis relies upon identifying large deviations decay rates of the non-overlapping probability of spheres whose centers are distributed as a homogeneous PPP.

Keywords

Exact simulationdominated coupling from the pastlarge deviationsnon-overlapping probability

MSC classification

Primary: 65C05: Monte Carlo methods
Secondary: 60G55: Point processes 60F10: Large deviations 68W40: Analysis of algorithms
Type
Original Article
Information
Advances in Applied Probability , Volume 53 , Issue 3 , September 2021 , pp. 839 - 885
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adams, D. J. (1974). Chemical potential of hard-sphere fluids by Monte Carlo methods. Molec. Phys. 28, 1241–1252.10.1080/00268977400102551CrossRefGoogle Scholar
Amorós, J. and Ravi, S. (2013). On the application of the Carnahan–Starling method for hard hyperspheres in several dimensions. Phys. Lett. A 377, 2089–2092.CrossRefGoogle Scholar
Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis Springer, New York.10.1007/978-0-387-69033-9CrossRefGoogle Scholar
Aurenhammer, F. (1987). Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 78–96.10.1137/0216006CrossRefGoogle Scholar
Baddeley, A. and Nair, G. (2012). Fast approximation of the intensity of Gibbs point processes. Electron. J. Statist. 6, 1155–1169.10.1214/12-EJS707CrossRefGoogle Scholar
Baranau, V. and Tallarek, U. (2016). Chemical potential and entropy in monodisperse and polydisperse hard-sphere fluids using Widom’s particle insertion method and a pore size distribution-based insertion probability. J. Chem. Phys. 144, 214503.CrossRefGoogle Scholar
Berthelsen, K. K. and Møller, J. (2006). Bayesian analysis of Markov point processes. In Case Studies in Spatial Point Process Modeling, Springer, New York, pp. 85–97.10.1007/0-387-31144-0_4CrossRefGoogle Scholar
Berthelsen, K. K. and Møller, J. (2008). Non-parametric Bayesian inference for inhomogeneous Markov point processes. Austral. N. Z. J. Statist. 50, 257–272.10.1111/j.1467-842X.2008.00516.xCrossRefGoogle Scholar
Boute, R. T. (1992). The Euclidean definition of the functions div and mod. ACM Trans. Program. Lang. Systems 14, 127–144.10.1145/128861.128862CrossRefGoogle Scholar
Dembo, A. and Zeitouni, O. (2010). Large Deviations Techniques and Applications. Springer, Berlin.10.1007/978-3-642-03311-7CrossRefGoogle Scholar
Devroye, L. (1986). Nonuniform Random Variate Generation. Springer, New York.10.1007/978-1-4613-8643-8CrossRefGoogle Scholar
Ferrari, P. A., Fernández, R. and Garcia, N. L. (2002). Perfect simulation for interacting point processes, loss networks and Ising models. Stoch. Process. Appl. 102, 63–88.10.1016/S0304-4149(02)00180-1CrossRefGoogle Scholar
Fill, J. A. (1998). An interruptible algorithm for perfect sampling via Markov chains. Ann. Appl. Prob. 8, 131–162.10.1214/aoap/1027961037CrossRefGoogle Scholar
Fill, J. A., Machida, M., Murdoch, D. J. and Rosenthal, J. S. (2000). Extension of Fill’s perfect rejection sampling algorithm to general chains. Random Structures Algorithms 17, 290–316.10.1002/1098-2418(200010/12)17:3/4<290::AID-RSA6>3.0.CO;2-Q3.0.CO;2-Q>CrossRefGoogle Scholar
Foss, S., Juneja, S., Mandjes, M. and Moka, S. (2015). Spatial loss systems: exact simulation and rare event behavior. ACM SIGMETRICS Performance Evaluation Rev. 43, 3–6.10.1145/2825236.2825238CrossRefGoogle Scholar
Garcia, N. L. (2000). Perfect simulation of spatial processes. Resenhas 4, 283–325.Google Scholar
Grimmett, G. (1999). Percolation, 2nd edn. Springer, Berlin.CrossRefGoogle Scholar
Haenggi, M. (2012). Stochastic Geometry for Wireless Networks. Cambridge University Press.10.1017/CBO9781139043816CrossRefGoogle Scholar
Häggström, O., van Lieshout, M.-C. N. and MØller, J. (1999). Characterization results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes. Bernoulli 5, 641–658.10.2307/3318694CrossRefGoogle Scholar
Hirsch, C., Moka, S. B., Taimre, T. and Kroese, D. P. (2021). Rare events in random geometric graphs. Methodology Comput. Appl. Prob., doi: 10.1007/s11009-021-09857-7.CrossRefGoogle Scholar
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13–30.CrossRefGoogle Scholar
Huber, M. L. (2012). Spatial birth–death swap chains. Bernoulli 18, 1031–1041.CrossRefGoogle Scholar
Huber, M. L. (2016). Perfect Simulation. CRC Press, Boca Raton, FL.CrossRefGoogle Scholar
Juneja, S. and Mandjes, M. (2013). Overlap problems on the circle. Adv. Appl. Prob. 45, 773–790.10.1239/aap/1377868538CrossRefGoogle Scholar
Kendall, W. S. (1998). Perfect simulation for the area-interaction point process. In Probability towards 2000 (New York, 1995) (Lecture Notes Statist., Vol. 128), Springer, New York, pp. 218–234.CrossRefGoogle Scholar
Kendall, W. S. (2015). Introduction to coupling-from-the-past using R. In Stochastic Geometry, Spatial Statistics and Random Fields (Lecture Notes Math., Vol. 2120), Springer, Cham, pp. 405–439.Google Scholar
Kendall, W. S. and Møller, J. (2000). Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. Appl. Prob. 32, 844–865.CrossRefGoogle Scholar
Lieb, E. and Mattis, D. (1966). Mathematical Physics in One Dimension: Exactly Soluble Models of Interacting Particles. Academic Press, New York.Google Scholar
Mase, S. et al. (2001). Packing densities and simulated tempering for hard core Gibbs point processes. Ann. Inst. Statist. Math. 53, 661–680.10.1023/A:1014662415827CrossRefGoogle Scholar
Mayer, J. and Mayer, M. (1940). Statistical Mechanics. John Wiley, New York.Google Scholar
Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge University Press.CrossRefGoogle Scholar
Møller, J., Huber, M. L. and Wolpert, R. L. (2010). Perfect simulation and moment properties for the Matérn type III process. Stoch. Process. Appl. 120, 2142–2158.CrossRefGoogle Scholar
Møller, J. and HelisovÁ, K. (2008). Power diagrams and interaction processes for unions of discs. Adv. Appl. Prob. 40, 321–347.CrossRefGoogle Scholar
Møller, J., Pettitt, A. N., Reeves, R. and Berthelsen, K. K. (2006). An efficient Markov chain Monte Carlo method for distributions with intractable normalising constants. Biometrika 93, 451–458.CrossRefGoogle Scholar
Pathria, R. (1972). Statistical Mechanics. Elsevier, Amsterdam.Google Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
Salsburg, Z. W., Zwanzig, R. W. and Kirkwood, J. G. (1953). Molecular distribution functions in a one-dimensional fluid. J. Chem. Phys. 21, 1098–1107.10.1063/1.1699116CrossRefGoogle Scholar
Senger, B., Voegel, J.-C. and Schaaf, P. (2000). Irreversible adsorption of colloidal particles on solid substrates. Colloids Surfaces A 165, 255–285.CrossRefGoogle Scholar
Stoyan, D., Kendall, W. S. and Mecke, J. (1987). Stochastic Geometry and Its Applications. John Wiley, Chichester.Google Scholar
Tarjus, G., Schaaf, P. and Talbot, J. (1990). Generalized random sequential adsorption. J. Chem. Phys. 93, 8352–8360.CrossRefGoogle Scholar
Thönnes, E. (1999). Perfect simulation of some point processes for the impatient user. Adv. Appl. Prob. 31, 69–87.CrossRefGoogle Scholar