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

Sarat Moka, Sandeep Juneja, Michel Mandjes

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)839-885
Number of pages47
JournalAdvances in Applied Probability
Issue number3
Publication statusPublished - Sept 2021
Externally publishedYes


  • Exact simulation
  • dominated coupling from the past
  • large deviations
  • nonoverlapping probability


Dive into the research topics of 'Rejection-and importance-sampling-based perfect simulation for Gibbs hard-sphere models'. Together they form a unique fingerprint.

Cite this