Rare events in random geometric graphs

DOI10.1007/S11009-021-09857-7MaRDI QIDQ2157382zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1334603 (Why is no real title available?)
• scientific article; zbMATH DE number 1912119 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• 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
• Efficient rare-event simulation for the maximum of heavy-tailed random walks
• 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
• Lectures on the Poisson Process
• Localization in random geometric graphs with too many edges
• Stochastic geometry and wireless networks. Volume I. Theory
• The importance sampling technique for understanding rare events in Erdős-Rényi random graphs

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)