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

DOI10.1007/S11222-021-10055-1zbMATH Open1475.62018arXiv2101.09514OpenAlexW3207464738MaRDI QIDQ2058910FDOQ2058910

Authors: Nadhir Ben Rached, Abdul-Lateef Haji-Ali, Gerardo Rubino, R. Tempone 

Publication date: 10 December 2021

Published in: Statistics and Computing (Search for Journal in Brave)

Abstract: We discuss estimating the probability that the sum of nonnegative independent and identically distributed random variables falls below a given threshold, i.e., $mathbbP(su{m}_{i=1}^N{X}_{i}leqgamma)$, 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 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 $X_i$ 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 $xightarrow0$, to $b{x}^p$, 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 $gamma$ 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 $gamma$.

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

Recommendations

• Uniformly Efficient Importance Sampling for the Tail Distribution of Sums of Random Variables
• Importance sampling for sums of random variables with regularly varying tails
• On the generalization of the hazard rate twisting-based simulation approach
• Efficient rare event simulation for heavy-tailed compound sums
• Importance sampling in rare event simulation

zbMATH Keywords

importance samplingrare eventexponential twistinggamma is PDF

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Applications of statistics in engineering and industry; control charts (62P30) Monte Carlo methods (65C05)

Cites Work

• Table of integrals, series, and products. Translated from the Russian. Translation edited and with a preface by Alan Jeffrey and Daniel Zwillinger. With one CD-ROM (Windows, Macintosh and UNIX)
• Stochastic simulation: Algorithms and analysis
• Exponential family techniques for the lognormal left tail
• Handbook of Monte Carlo Methods
• Rare Event Simulation using Monte Carlo Methods
• Simulating heavy tailed processes using delayed hazard rate twisting
• Fast and accurate computation of the distribution of sums of dependent log-normals
• Multilevel sequential Monte Carlo samplers
• On the efficient simulation of the left-tail of the sum of correlated log-normal variates
• On the generalization of the hazard rate twisting-based simulation approach
• Tail behavior of sums and differences of log-normal random variables
• Unbiased estimation of the gradient of the log-likelihood in inverse problems

Cited In (12)

• Counterexamples in importance sampling for large deviations probabilities
• Automated importance sampling via optimal control for stochastic reaction networks: a Markovian projection-based approach
• Learning-based importance sampling via stochastic optimal control for stochastic reaction networks
• Estimation and approximation of densities of i.i.d. sums via importance sampling.
• Importance sampling for maxima on trees
• Importance Sampling via Load-Balanced Facility Location
• Efficient large deviation estimation based on importance sampling
• Efficient simulated maximum likelihood estimation through explicitly parameter dependent importance sampling
• Efficient importance sampling in mixture frameworks
• Efficient exponential tilting with applications
• Uniformly Efficient Importance Sampling for the Tail Distribution of Sums of Random Variables
• State-dependent importance sampling for estimating expectations of functionals of sums of independent random variables

This page was built for publication: Efficient importance sampling for large sums of independent and identically distributed random variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2058910)