MaPhySto
The Danish National Research Foundation:
Network in Mathematical Physics and Stochastics

MPS-RR 2004-3
February 2004

# Improved Algorithms for Rare Event Simulation with Heavy Tails

by: Søren Asmussen, Dirk P. Kroese

## Abstract

The estimation of $\mathbf{P}(S_n > u)$ by simulation where $S_n$ is a sum of i.i.d. r.v.'s $Y_1,..., Y_n$ is of importance in many applications. We propose two simulation estimators based upon the identity $\mathbf{P}(S_n > u) = n \mathbf{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), the other 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 where $n$ is replaced by an independent geometric r.v. $N$. The conclusion is that the new estimators compare extremely favourable 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.

Availability: [ gzipped ps-file ] [ pdf-file ]