Rare events in random geometric graphs

DOI10.1007/S11009-021-09857-7zbMATH Open1491.60043arXiv2007.05965OpenAlexW3161687654MaRDI QIDQ2157382FDOQ2157382

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

Publication date: 28 July 2022

Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)

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 leverage 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.

Full work available at URL: https://arxiv.org/abs/2007.05965

Recommendations

• Small variance estimators for rare event probabilities
• Localization in random geometric graphs with too many edges
• Rare-event probability estimation with conditional Monte Carlo
• Random Geometric Graphs
• Importance sampling for multi-constraints rare event probability

zbMATH Keywords

random geometric graphrare eventStrauss processconditional Monte Carlo

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient rare-event simulation for the maximum of heavy-tailed random walks
• Stochastic geometry and wireless networks. Volume I. Theory
• Handbook of Monte Carlo Methods
• Improved algorithms for rare event simulation with heavy tails
• Large deviation principles for Euclidean functionals and other nearly additive processes
• A general framework for consistent estimation of charge transport properties via random walks in random environments
• A review of conditional rare event simulation for tail probabilities of heavy tailed random variables
• Localization in random geometric graphs with too many edges
• The importance sampling technique for understanding rare events in Erdős-Rényi random graphs
• Lectures on the Poisson Process
• Title not available (Why is that?)

Cited In (4)

• Localization in random geometric graphs with too many edges
• Rejection- and importance-sampling-based perfect simulation for Gibbs hard-sphere models
• Rare events for the Manneville-Pomeau map
• Rare event asymptotics for exploration processes for random graphs

This page was built for publication: Rare events in random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2157382)