Funded by The Danish National Research Foundation

MPS-RR 2004-3

February 2004

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 ]