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

1 Citation (Scopus)

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
Pages (from-to)1367-1383
Number of pages17
JournalMethodology and Computing in Applied Probability
Volume24
Issue number3
Early online date4 May 2021
DOIs
Publication statusPublished - Sep 2022
Externally publishedYes

Bibliographical note

© The Author(s) 2021. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

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