State-independent Importance Sampling for Estimating Large Deviation Probabilities in Heavy-tailed Random Walks

Efficient simulation of rare events involving sums of heavy-tailed random variables has been an active research area in applied probability over the last fifteen years. These problems are viewed as challenging, since large deviations theory inspired and exponential twisting based importance sampling distributions that work well for rare events involving sums of light tailed random variables fail in these settings. Moreover, there exist negative results suggesting that state-independent importance sampling methods that work well in light-tailed settings fail for certain rare events involving sums of heavy-tailed random variables. This has led to the development of growing literature for efficiently simulating such events using more nuanced, and in many cases, computationally demanding state-dependent importance sampling methods. In this article we shed new light on this issue by observing that simpler state-independent exponential twisting based importance sampling methods, suitably adjusted in the tails, can provide strongly efficient algorithms to estimate such rare event probabilities. Specifically, we develop strongly efficient state-independent importance sampling algorithms for the classical large deviations probability that sums of independent, identically distributed random variables with regularly varying tails exceed an increasing threshold both in the case where the number of random variables increases to infinity and when it is fixed.