×

Rare events in random geometric graphs. (English) Zbl 1491.60043

Summary: 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.

MSC:

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

References:

[1] Asmussen, S.; Kroese, DP, Improved algorithms for rare event simulation with heavy tails, Adv Appl Probab, 38, 2, 545-558 (2006) · Zbl 1097.65017 · doi:10.1239/aap/1151337084
[2] Baccelli F, Błaszczyszyn B (2009) Stochastic Geometry and Wireless Networks. Now Publishers Inc · Zbl 1184.68015
[3] Baddeley, A.; Nair, G., Approximating the moments of a spatial point process, Stat, 1, 1, 18-30 (2012) · Zbl 07847456 · doi:10.1002/sta4.5
[4] Bhamidi, S.; Hannig, J.; Lee, CY; Nolen, J., The importance sampling technique for understanding rare events in Erdȯs-Rényi random graphs, Electron J Probab., 20, 107, 30 (2015) · Zbl 1327.05300
[5] Billingsley, P., Probability and measure (1995), New York: Wiley, New York · Zbl 0822.60002
[6] Blanchet, J.; Glynn, P., Efficient rare-event simulation for the maximum of heavy-tailed random walks, Ann Appl Probab, 18, 4, 1351-1378 (2008) · Zbl 1147.60315 · doi:10.1214/07-AAP485
[7] Chatterjee, S.; Harel, M., Localization in random geometric graphs with too many edges, Ann Probab, 48, 2, 574-621 (2020) · Zbl 1446.60024
[8] Keeler HP, Jahnel B, Maye O, Aschenbach D, Brzozowski M (2018) Disruptive events in high-density cellular networks. 16th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt)
[9] Kroese, DP; Taimre, T.; Botev, ZI, Handbook of monte carlo methods (2013), New York: Wiley, New York · Zbl 1213.65001
[10] Last, G.; Penrose, MD, Lectures on the poisson process (2017), Cambridge: Cambridge University Press, Cambridge · Zbl 1392.60004 · doi:10.1017/9781316104477
[11] Lomonosov, M.; Shpungin, Y., Combinatorics of reliability Monte Carlo, Random Struct Algorithm, 14, 4, 329-343 (1999) · Zbl 0952.60088 · doi:10.1002/(SICI)1098-2418(199907)14:4<329::AID-RSA3>3.0.CO;2-X
[12] Møller J, Waagepetersen RP (2004) Statistical inference and simulation for spatial point processes. CRC, Boca Raton · Zbl 1044.62101
[13] Rojas-Nandayapa, L., A review of conditional rare event simulation for tail probabilities of heavy tailed random variables, Bol Soc Mat Mex (3), 19, 2, 159-182 (2013) · Zbl 1311.60050
[14] Seppäläinen, T.; Yukich, JE, Large deviation principles for Euclidean functionals and other nearly additive processes, Probab Theory Rel Fields, 120, 3, 309-345 (2001) · Zbl 0984.60038 · doi:10.1007/PL00008785
[15] Stenzel, O.; Hirsch, C.; Brereton, T.; Baumeier, T.; Andrienko, D.; Kroese, DP; Schmidt, V., A general framework for consistent estimation of charge transport properties via random walks in random environments, Multiscale Model Simul, 12, 1108-1134 (2014) · Zbl 1311.05174 · doi:10.1137/130942504
[16] Vaisman, R.; Kroese, DP; Gertsbakh, IB, Improved sampling plans for combinatorial invariants of coherent systems, IEEE Trans Rel, 65, 1, 410-424 (2015) · doi:10.1109/TR.2015.2446471
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.