TY - JOUR

T1 - Efficient importance sampling for large sums of independent and identically distributed random variables

AU - Ben Rached, Nadhir

AU - Haji-Ali, Abdul Lateef

AU - Rubino, Gerardo

AU - Tempone, Raul

N1 - KAUST Repository Item: Exported on 2021-10-22
Acknowledged KAUST grant number(s): OSR-2019-CRG8-4033
Acknowledgements: This publication is based upon work supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) under Award No. OSR-2019-CRG8-4033 and the Alexander von Humboldt Foundation. A-L. Haji-Ali was supported by a Sabbatical Grant from the Royal Society of Edinburgh.

PY - 2021/10/11

Y1 - 2021/10/11

N2 - We discuss estimating the probability that the sum of nonnegative independent and identically distributed random variables falls below a given threshold, i.e., P(∑i=1NXi≤γ), via importance sampling (IS). We are particularly interested in the rare event regime when N is large and/or γ is small. The exponential twisting is a popular technique for similar problems that, in most cases, compares favorably to other estimators. However, it has some limitations: (i) It assumes the knowledge of the moment-generating function of Xi and (ii) sampling under the new IS PDF is not straightforward and might be expensive. The aim of this work is to propose an alternative IS PDF that approximately yields, for certain classes of distributions and in the rare event regime, at least the same performance as the exponential twisting technique and, at the same time, does not introduce serious limitations. The first class includes distributions whose probability density functions (PDFs) are asymptotically equivalent, as x→ 0 , to bxp, for p> - 1 and b> 0. For this class of distributions, the Gamma IS PDF with appropriately chosen parameters retrieves approximately, in the rare event regime corresponding to small values of γ and/or large values of N, the same performance of the estimator based on the use of the exponential twisting technique. In the second class, we consider the Log-normal setting, whose PDF at zero vanishes faster than any polynomial, and we show numerically that a Gamma IS PDF with optimized parameters clearly outperforms the exponential twisting IS PDF. Numerical experiments validate the efficiency of the proposed estimator in delivering a highly accurate estimate in the regime of large N and/or small γ.

AB - We discuss estimating the probability that the sum of nonnegative independent and identically distributed random variables falls below a given threshold, i.e., P(∑i=1NXi≤γ), via importance sampling (IS). We are particularly interested in the rare event regime when N is large and/or γ is small. The exponential twisting is a popular technique for similar problems that, in most cases, compares favorably to other estimators. However, it has some limitations: (i) It assumes the knowledge of the moment-generating function of Xi and (ii) sampling under the new IS PDF is not straightforward and might be expensive. The aim of this work is to propose an alternative IS PDF that approximately yields, for certain classes of distributions and in the rare event regime, at least the same performance as the exponential twisting technique and, at the same time, does not introduce serious limitations. The first class includes distributions whose probability density functions (PDFs) are asymptotically equivalent, as x→ 0 , to bxp, for p> - 1 and b> 0. For this class of distributions, the Gamma IS PDF with appropriately chosen parameters retrieves approximately, in the rare event regime corresponding to small values of γ and/or large values of N, the same performance of the estimator based on the use of the exponential twisting technique. In the second class, we consider the Log-normal setting, whose PDF at zero vanishes faster than any polynomial, and we show numerically that a Gamma IS PDF with optimized parameters clearly outperforms the exponential twisting IS PDF. Numerical experiments validate the efficiency of the proposed estimator in delivering a highly accurate estimate in the regime of large N and/or small γ.

UR - http://hdl.handle.net/10754/667225

UR - https://link.springer.com/10.1007/s11222-021-10055-1

UR - http://www.scopus.com/inward/record.url?scp=85116736382&partnerID=8YFLogxK

U2 - 10.1007/s11222-021-10055-1

DO - 10.1007/s11222-021-10055-1

M3 - Article

VL - 31

JO - Statistics and Computing

JF - Statistics and Computing

SN - 1573-1375

IS - 6

ER -