Rare events in random geometric graphs

Christian Hirsch*, Sarat B. Moka, Thomas Taimre, Dirk P. Kroese

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

This work introduces and compares approaches for estimating rare-event probabilities related to the number of edges in the random geometric graph on a Poisson point process. In the one-dimensional setting, we derive closed-form expressions for a variety of conditional probabilities related to the number of edges in the random geometric graph and develop conditional Monte Carlo algorithms for estimating rare-event probabilities on this basis. We prove rigorously a reduction in variance when compared to the crude Monte Carlo estimators and illustrate the magnitude of the improvements in a simulation study. In higher dimensions, we use conditional Monte Carlo to remove the fluctuations in the estimator coming from the randomness in the Poisson number of nodes. Finally, building on conceptual insights from large-deviations theory, we illustrate that importance sampling using a Gibbsian point process can further substantially reduce the estimation variance.

Original languageEnglish
Number of pages17
JournalMethodology and Computing in Applied Probability
DOIs
Publication statusE-pub ahead of print - 4 May 2021
Externally publishedYes

Keywords

  • Rare event
  • Random geometric graph
  • Conditional Monte Carlo
  • Strauss process

Fingerprint

Dive into the research topics of 'Rare events in random geometric graphs'. Together they form a unique fingerprint.

Cite this