Efficient Importance Sampling for Large Sums of Independent and Identically Distributed Random Variables

We aim to estimate the probability that the sum of nonnegative independent and identically distributed random variables falls below a given threshold, i.e., $mathbb{P}(sum_{i=1}^{N}{X_i} leq gamma)$, via importance sampling (IS). We are particularly interested in the rare event regime when $N$ is large and/or $gamma$ is small. The exponential twisting is a popular technique that, in most of the cases, compares favorably to existing estimators. However, it has several limitations: i) it assumes the knowledge of the moment generating function of $X_i$ and ii) sampling under the new measure is not straightforward and might be expensive. The aim of this work is to propose an alternative change of measure that yields, in the rare event regime corresponding to large $N$ and/or small $gamma$, at least the same performance as the exponential twisting technique and, at the same time, does not introduce serious limitations. For distributions whose probability density functions (PDFs) are $mathcal{O}(x^{d})$, as $x rightarrow 0$ and $d>-1$, we prove that the Gamma IS PDF with appropriately chosen parameters retrieves asymptotically, in the rare event regime, the same performance of the estimator based on the use of the exponential twisting technique. Moreover, in the Log-normal setting, where the PDF at zero vanishes faster than any polynomial, we numerically show that a Gamma IS PDF with optimized parameters clearly outperforms the exponential twisting change of measure. Numerical experiments validate the efficiency of the proposed estimator in delivering a highly accurate estimate in the regime of large $N$ and/or small $gamma$.