On the Efficiency Loss of State-Independent Importance Sampling in the Presence of Heavy-Tails, Operations Research Letters
We consider importance sampling simulation for estimating rare event probabilities in the presence of heavy-tailed distributions that have polynomial-like tails. In particular, we prove the following negative result: there does not exist an asymptotically optimal state-independent change-of-measure for estimating the probability that a random walk (respectively, queue length for a single server queue) exceeds a "high" threshold before going below zero (respectively, becoming empty). Furthermore, we derive explicit bounds on the best asymptotic variance reduction achieved by importance sampling relative to naive simulation. We illustrate through a simple numerical example that a good" state-dependent change-of-measure may be developed based on an approximation of the zero-variance measure
Achal Bassamboo, Sandeep Juneja, Assaf Zeevi
Bassamboo, Achal, Sandeep Juneja, and Assaf Zeevi. 2007. On the Efficiency Loss of State-Independent Importance Sampling in the Presence of Heavy-Tails. Operations Research Letters. 35(2): 251-260.