Improved algorithms for rare event simulation with heavy tails

Abstract

The estimation of P( S n > u ) by simulation, where S n is the sum of independent, identically distributed random varibles Y 1 ,…, Y n , is of importance in many applications. We propose two simulation estimators based upon the identity P( S n > u )= n P( S n > u , M n = Y n ), where M n =max( Y 1 ,…, Y n ). One estimator uses importance sampling (for Y n only), and the other uses conditional Monte Carlo conditioning upon Y 1 ,…, Y n −1 . Properties of the relative error of the estimators are derived and a numerical study given in terms of the M/G/1 queue in which n is replaced by an independent geometric random variable N . The conclusion is that the new estimators compare extremely favorably with previous ones. In particular, the conditional Monte Carlo estimator is the first heavy-tailed example of an estimator with bounded relative error. Further improvements are obtained in the random- N case, by incorporating control variates and stratification techniques into the new estimation procedures.