State-independent Importance Sampling for Regularly Varying Random Walks

Efficient simulation of rare events involving sums of heavy-tailed random variables has been an active research area in applied probability in the last fifteen years. These rare events arise in many applications including telecommunications, computer and communication networks, insurance and finance. These problems are viewed as challenging, since large deviations theory inspired and exponential twisting based importance sampling algorithms that work well for rare events involving sums of light tailed random variables fail in these settings.

In this talk we shall discuss about developing some simple state-independent exponential twisting based importance sampling methods to efficiently estimate such rare event probabilities. Specifically, we develop strongly efficient algorithms for estimating:

1. The classical large deviations probability that the 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.

2. Finite-horizon level crossing probabilities for negative-mean regularly varying random walks

Accurate computation of these level crossing probabilities has applications in estimating ruin probabilities in insurance settings and calculating waiting times in GI/G/1 queues.