“ State-dependent Importance Sampling with Application to Rare-event Simulation ”

Abstract

Importance sampling is one of the most important variance reduction techniques for Monte Carlo integration. The “best importance sampling algorithm”, which yields zero computation error, is conceptually known. Though not implementable, this “best algorithm” provides guidelines on the efficient Monte Carlo designs, the central issue of which is to find an implementable algorithm to approximate this gold standard. Based on this intuition, we introduce the first provably efficient simulation algorithm to compute the probability that a customer experiences long delay in a positive recurrent two-server (G/G/2) queue with heavy-tailed service requirement. In particular, our algorithm is based on a family of sampling distributions that approximates the “best sampling distribution” well. In addition, the proposed family of distributions turns out to be very powerful and solved a large collection of heavy-tailed rare-event simulation problems.