## Efficient Rare-event Simulation for the Maximum of Heavy-tailed Random Walks
*J. Blanchet and P. W. Glynn*
*Annals of Applied Probability*, Vol. 18, No. 4, 1351-1378 (2008)
Let (X_{n}: n ≥ 0) be a sequence of i.i.d. r.v.’s with negative mean. Set
S0 = 0 and define S_{n} = X_{1} +· · ·+X_{n}. We propose an importance sampling
algorithm to estimate the tail of M = max{S_{n}: n ≥ 0} that is strongly efficient
for both light and heavy-tailed increment distributions. Moreover, in the case
of heavy-tailed increments and under additional technical assumptions, our
estimator can be shown to have asymptotically vanishing relative variance
in the sense that its coefficient of variation vanishes as the tail parameter increases.
A key feature of our algorithm is that it is state-dependent. In the
presence of light tails, our procedure leads to Siegmund’s (1979) algorithm.
The rigorous analysis of efficiency requires new Lyapunov-type inequalities
that can be useful in the study of more general importance sampling algorithms.
## |