{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:45:29Z","timestamp":1740123929835,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T00:00:00Z","timestamp":1729296000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T00:00:00Z","timestamp":1729296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005366","name":"University of Oslo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005366","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a flexible, deterministic numerical method for computing left-tail rare events of sums of non-negative, independent random variables. The method is based on iterative numerical integration of linear convolutions by means of Newtons\u2013Cotes rules. The periodicity properties of convoluted densities combined with the Trapezoidal rule are exploited to produce a robust and efficient method, and the method is flexible in the sense that it can be applied to all kinds of non-negative continuous RVs. We present an error analysis and study the benefits of utilizing Newton\u2013Cotes rules versus the fast Fourier transform (FFT) for numerical integration, showing that although there can be efficiency benefits to using FFT, Newton\u2013Cotes rules tend to preserve the relative error better, and indeed do so at an acceptable computational cost. Numerical studies on problems with both known and unknown rare-event probabilities showcase the method\u2019s performance and support our theoretical findings.\n<\/jats:p>","DOI":"10.1007\/s11222-024-10514-5","type":"journal-article","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T10:02:10Z","timestamp":1729332130000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A fast and accurate numerical method for the left tail of sums of independent random variables"],"prefix":"10.1007","volume":"34","author":[{"given":"Nadhir","family":"Ben\u00a0Rached","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H\u00e5kon","family":"Hoel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes Vincent","family":"Meo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,19]]},"reference":[{"issue":"2","key":"10514_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1515\/mcma-2018-0009","volume":"24","author":"MS Alouini","year":"2018","unstructured":"Alouini, M.S., Nadhir, B.R., Abla, K., Raul, T.: On the efficient simulation of the left-tail of the sum of correlated log-normal variates. Mt. Carlo Methods Appl. 24(2), 101\u2013115 (2018)","journal-title":"Mt. Carlo Methods Appl."},{"issue":"2","key":"10514_CR2","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/s11222-022-10202-2","volume":"33","author":"EB Amar","year":"2023","unstructured":"Amar, E.B., Rached, N.B., Haji-Ali, A.L., Tempone, R.: State-dependent importance sampling for estimating expectations of functionals of sums of independent random variables. Stat. Comput. 33(2), 40 (2023)","journal-title":"Stat. Comput."},{"key":"10514_CR3","doi-asserted-by":"crossref","unstructured":"Asmussen, S., Glynn, P.W.: Stochastic simulation: algorithms and analysis. In: Stochastic Modelling and Applied Probability, Springer, New York (2007)","DOI":"10.1007\/978-0-387-69033-9"},{"key":"10514_CR4","doi-asserted-by":"crossref","unstructured":"Asmussen, S., Goffard, P., Laub, P.J.: Orthonormal Polynomial Expansions and Lognormal Sum Densities. Chapter 6, pp. 127\u2013150 (2019)","DOI":"10.1142\/9781786341952_0008"},{"key":"10514_CR5","doi-asserted-by":"crossref","unstructured":"Asmussen, S., Kortschak, D.: On error rates in rare event simulation with heavy tails. In: Proceedings of the 2012 Winter Simulation Conference (WSC), IEEE, pp. 1\u201311 (2012)","DOI":"10.1109\/WSC.2012.6465288"},{"issue":"2","key":"10514_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.2143\/AST.27.2.542054","volume":"27","author":"S Asmussen","year":"1997","unstructured":"Asmussen, S., Binswanger, K.: Simulation of ruin probabilities for subexponential claims. ASTIN Bull. J. IAA 27(2), 297\u2013318 (1997)","journal-title":"ASTIN Bull. J. IAA"},{"issue":"2","key":"10514_CR7","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1239\/aap\/1151337084","volume":"38","author":"S Asmussen","year":"2006","unstructured":"Asmussen, S., Kroese, D.P.: Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Probab. 38(2), 545\u2013558 (2006)","journal-title":"Adv. Appl. Probab."},{"key":"10514_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10479-009-0658-5","volume":"189","author":"S\u00f8ren Asmussen","year":"2011","unstructured":"Asmussen, S\u00f8ren., Blanchet, Jos\u00e9, Juneja, Sandeep, Rojas-Nandayapa, Leonardo: Efficient simulation of tail probabilities of sums of correlated lognormals. Ann. Oper. Res. 189, 5\u201323 (2011)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"10514_CR9","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1111\/sjos.12203","volume":"43","author":"S Asmussen","year":"2016","unstructured":"Asmussen, S., Jens, L.J., Leonardo, R.N.: Exponential family techniques for the lognormal left tail. Scand. J. Stat. 43(3), 774\u2013787 (2016)","journal-title":"Scand. J. Stat."},{"key":"10514_CR10","doi-asserted-by":"crossref","unstructured":"Beaulieu, N.C., Gan, L.: Improving simulation of lognormal sum distributions with hyperspace replication. In: IEEE Global Communications Conference (GLOBECOM), vol. 2019, pp. 1\u20137 (2019)","DOI":"10.1109\/GLOBECOM38437.2019.9014029"},{"issue":"3","key":"10514_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1109\/TCOMM.2008.060123","volume":"56","author":"NC Beaulieu","year":"2008","unstructured":"Beaulieu, N.C.: Fast convenient numerical computation of lognormal characteristic functions. IEEE Trans. Commun. 56(3), 331\u2013333 (2008)","journal-title":"IEEE Trans. Commun."},{"issue":"12","key":"10514_CR12","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1109\/LCOMM.2004.837657","volume":"8","author":"NC Beaulieu","year":"2004","unstructured":"Beaulieu, N.C., Rajwani, F.: Highly accurate simple closed-form approximations to lognormal sum distributions and densities. IEEE Commun. Lett. 8(12), 709\u2013711 (2004)","journal-title":"IEEE Commun. Lett."},{"issue":"2","key":"10514_CR13","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1109\/TVT.2004.823494","volume":"53","author":"NC Beaulieu","year":"2004","unstructured":"Beaulieu, N.C., Xie, Q.: An optimal lognormal approximation to lognormal sum distributions. IEEE Trans. Veh. Technol. 53(2), 479\u2013489 (2004)","journal-title":"IEEE Trans. Veh. Technol."},{"issue":"9","key":"10514_CR14","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1109\/LCOMM.2009.091288","volume":"13","author":"M Di Renzo","year":"2009","unstructured":"Di Renzo, M., Imbriglio, L., Graziosi, F., Santucci, F.: Smolyak\u2019s algorithm: a simple and accurate framework for the analysis of correlated log-normal power-sums. IEEE Commun. Lett. 13(9), 673\u2013675 (2009)","journal-title":"IEEE Commun. Lett."},{"key":"10514_CR15","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.insmatheco.2019.10.003","volume":"90","author":"E Furman","year":"2020","unstructured":"Furman, E., Hackmann, D., Alexey, K.: On log-normal convolutions: an analytical-numerical method with applications to economic capital determination. Insur. Math. Econom. 90, 120\u2013134 (2020)","journal-title":"Insur. Math. Econom."},{"key":"10514_CR16","volume-title":"Table of Integrals, Series, and Products","author":"IS Gradshteyn","year":"2007","unstructured":"Gradshteyn, I.S., Ryzhik, I.M.: Table of Integrals, Series, and Products, 7th edn. Elsevier\/Academic Press, Amsterdam (2007)","edition":"7"},{"issue":"1","key":"10514_CR17","doi-asserted-by":"publisher","first-page":"444","DOI":"10.3150\/14-BEJ665","volume":"22","author":"A Gulisashvili","year":"2016","unstructured":"Gulisashvili, A., Tankov, P.: Tail behavior of sums and differences of log-normal random variables. Bernoulli 22(1), 444\u2013493 (2016)","journal-title":"Bernoulli"},{"issue":"2","key":"10514_CR18","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1109\/LWC.2016.2516543","volume":"5","author":"S Guruacharya","year":"2016","unstructured":"Guruacharya, S., Tabassum, H., Hossain, E.: Saddle point approximation for outage probability using cumulant generating functions. IEEE Wirel. Commun. Lett. 5(2), 192\u2013195 (2016)","journal-title":"IEEE Wirel. Commun. Lett."},{"key":"10514_CR19","volume-title":"Analysis of Numerical Methods","author":"E Isaacson","year":"2012","unstructured":"Isaacson, E., Keller, H.B.: Analysis of Numerical Methods. Courier Corporation, Chelmsford (2012)"},{"key":"10514_CR20","doi-asserted-by":"crossref","unstructured":"Jingxian, W., Mehta, N.B., Jin Z.: Flexible lognormal sum approximation method, GLOBECOM \u201905. In: IEEE Global Telecommunications Conference, vol. 6, pp. 3413\u20133417 (2005)","DOI":"10.1109\/GLOCOM.2005.1578407"},{"issue":"3","key":"10514_CR21","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1109\/LSP.2008.2012223","volume":"16","author":"AL-S Jos\u00e9","year":"2009","unstructured":"Jos\u00e9, A.L.-S.: Simple closed-form approximation to Ricean sum distributions. IEEE Signal Process. Lett. 16(3), 153\u2013155 (2009)","journal-title":"IEEE Signal Process. Lett."},{"issue":"2","key":"10514_CR22","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/566392.566394","volume":"12","author":"S Juneja","year":"2002","unstructured":"Juneja, S., Shahabuddin, P.: Simulating heavy tailed processes using delayed hazard rate twisting. ACM Trans. Model. Comput. Simul. (TOMACS) 12(2), 94\u2013118 (2002)","journal-title":"ACM Trans. Model. Comput. Simul. (TOMACS)"},{"key":"10514_CR23","unstructured":"Karthyek Rajhaa, A.M., Juneja, S.: State-independent importance sampling for estimating large deviation probabilities in heavy-tailed random walks. In: 6th International ICST Conference on Performance Evaluation Methodologies and Tools, pp.\u00a0127\u2013135 (2012)"},{"issue":"4","key":"10514_CR24","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1089\/cmb.2005.12.416","volume":"12","author":"U Keich","year":"2005","unstructured":"Keich, U.: sFFT: a faster accurate computation of the p-value of the entropy score. J. Comput. Biol. 12(4), 416\u2013430 (2005)","journal-title":"J. Comput. Biol."},{"key":"10514_CR25","doi-asserted-by":"publisher","DOI":"10.1002\/9781118014967","volume-title":"Handbook of Monte Carlo Methods","author":"DP Kroese","year":"2011","unstructured":"Kroese, D.P., Taimre, T., Botev, Z.I.: Handbook of Monte Carlo Methods. Wiley, Hoboken (2011)"},{"key":"10514_CR26","unstructured":"LLC Advanpix, Multiprecision computing toolbox for matlab (2006)"},{"issue":"1","key":"10514_CR27","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/MAP.2007.370983","volume":"49","author":"DY Michel","year":"2007","unstructured":"Michel, D.Y.: The $$\\kappa -\\mu $$ distribution and the $$\\eta -\\mu $$ distribution. IEEE Antennas Propag. Mag. 49(1), 68\u201381 (2007)","journal-title":"IEEE Antennas Propag. Mag."},{"issue":"6","key":"10514_CR28","doi-asserted-by":"publisher","first-page":"2583","DOI":"10.1109\/TCOMM.2017.2669979","volume":"65","author":"BR Nadhir","year":"2017","unstructured":"Nadhir, B.R., Abla, K., Mohamed-Slim, A., Raul, T.: On the efficient simulation of outage probability in a log-normal fading environment. IEEE Trans. Commun. 65(6), 2583\u20132593 (2017)","journal-title":"IEEE Trans. Commun."},{"key":"10514_CR29","doi-asserted-by":"crossref","unstructured":"Norman, C.: On the marcum Q-function behavior of the left tail probability of the lognormal sum distribution. In: ICC 2020\u20132020 IEEE International Conference on Communications (ICC), pp.\u00a01\u20136 (2020)","DOI":"10.1109\/ICC40277.2020.9149127"},{"issue":"2","key":"10514_CR30","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1109\/JSTSP.2015.2500201","volume":"10","author":"BN Rached","year":"2016","unstructured":"Rached, B.N., Abla, K., Mohamed-Slim, A., Raul, T.: Unified importance sampling schemes for efficient simulation of outage capacity over generalized fading channels. IEEE J. Selected Topics Signal Process. 10(2), 376\u2013388 (2016)","journal-title":"IEEE J. Selected Topics Signal Process."},{"key":"10514_CR31","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s11222-016-9716-4","volume":"28","author":"BN Rached","year":"2018","unstructured":"Rached, B.N., Fatma, B., Abla, K., Mohamed-Slim, A., Raul, T.: On the generalization of the hazard rate twisting-based simulation approach. Stat. Comput. 28, 61\u201375 (2018)","journal-title":"Stat. Comput."},{"key":"10514_CR32","doi-asserted-by":"crossref","unstructured":"Saberali, S.A., Beaulieu, N.C.: New approximations to the lognormal characteristic function. In: 2012 IEEE Global Communications Conference (GLOBECOM), pp.\u00a02168\u20132172 (2012)","DOI":"10.1109\/GLOCOM.2012.6503436"},{"key":"10514_CR33","doi-asserted-by":"crossref","unstructured":"Senaratne, D., Tellambura, C.: A general numerical method for computing the probability of outage. In: IEEE Wireless Communications and Networking Conference, vol. 2009, pp. 1\u20136 (2009)","DOI":"10.1109\/WCNC.2009.4917505"},{"key":"10514_CR34","doi-asserted-by":"crossref","unstructured":"Senaratne, D., Tellambura, C.: Numerical computation of the lognormal sum distribution. In: GLOBECOM 2009\u20132009 IEEE Global Telecommunications Conference, pp.\u00a01\u20136 (2009)","DOI":"10.1109\/GLOCOM.2009.5425708"},{"key":"10514_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801181","volume-title":"An Introduction to Numerical Analysis","author":"E S\u00fcli","year":"2003","unstructured":"S\u00fcli, E., Mayers, D.F.: An Introduction to Numerical Analysis. Cambridge University Press, Cambridge (2003)"},{"key":"10514_CR36","doi-asserted-by":"crossref","unstructured":"Tellambura, C., Annamalai, A.: An unified numerical approach for computing the outage probability for mobile radio systems. IEEE Commun. Lett. 3(4), 97\u201399 (1999)","DOI":"10.1109\/4234.757200"},{"key":"10514_CR37","doi-asserted-by":"crossref","unstructured":"Tellambura, C., Senaratne, D.: Accurate computation of the MGF of the lognormal distribution and its application to sum of lognormals. IEEE Trans. Commun. 58(5), 1568\u20131577 (2010)","DOI":"10.1109\/TCOMM.2010.05.080640"},{"key":"10514_CR38","doi-asserted-by":"crossref","unstructured":"Thanh, V.P., Truong, C.T., Anh, T.P.: On the MGF-based approximation of the sum of independent gamma-gamma random variables. In: 2015 IEEE 81st Vehicular Technology Conference (VTC Spring), pp.\u00a01\u20135 (2015)","DOI":"10.1109\/VTCSpring.2015.7145970"},{"key":"10514_CR39","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.csda.2016.03.010","volume":"101","author":"H Wilson","year":"2016","unstructured":"Wilson, H., Keich, U.: Accurate pairwise convolutions of non-negative vectors via FFT. Comput. Stat. Data Anal. 101, 300\u2013315 (2016)","journal-title":"Comput. Stat. Data Anal."},{"issue":"1","key":"10514_CR40","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1080\/10618600.2016.1276841","volume":"26","author":"H Wilson","year":"2017","unstructured":"Wilson, H., Keich, U.: Accurate small tail probabilities of sums of iid lattice-valued random variables via FFT. J. Comput. Graph. Stat. 26(1), 223\u2013229 (2017)","journal-title":"J. Comput. Graph. Stat."},{"key":"10514_CR41","doi-asserted-by":"crossref","unstructured":"Xiao, Z., Zhu, B., Cheng, J., Wang, Y.: Outage probability bounds of EGC over dual-branch non-identically distributed independent lognormal fading channels with optimized parameters. IEEE Trans. Veh. Technol. 68(8), 8232\u20138237 (2019)","DOI":"10.1109\/TVT.2019.2923277"},{"key":"10514_CR42","doi-asserted-by":"crossref","unstructured":"Zhu, B., Zhang, Z., Wang, L., Dang, J., Liang, W., Cheng, J., Geoffrey Y.L.: Right tail approximation for the distribution of lognormal sum and its applications. In: IEEE GLOBECOM Workshops (GC Wkshps), vol. 2020, pp. 1\u20136 (2020)","DOI":"10.1109\/GCWkshps50303.2020.9367405"}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-024-10514-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11222-024-10514-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-024-10514-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T12:13:26Z","timestamp":1732536806000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11222-024-10514-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,19]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10514"],"URL":"https:\/\/doi.org\/10.1007\/s11222-024-10514-5","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"type":"print","value":"0960-3174"},{"type":"electronic","value":"1573-1375"}],"subject":[],"published":{"date-parts":[[2024,10,19]]},"assertion":[{"value":"2 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"202"}}