2008/07/21 by José Blanchet, Jose Blanchet, Peter W. Glynn +1 · 1 citation
Decision Sciences · Mathematics · #Markov Chains and Monte Carlo Methods #Probability and Risk Models #Stochastic processes and statistical mechanics #math.PR #msc:60G50 #msc:60G70 #msc:60J05 #msc:60J20 #msc:68W40
paper · pdf · doi:10.1214/07-aap485
published as Annals of Applied Probability 2008, Vol. 18, No. 4, 1351-1378 · Published in at http://dx.doi.org/10.1214/07-AAP485 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
openalex publication_date 2008/07/21 · arxiv created 2008/08/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let (Xn : n≥0) be a sequence of i.i.d. r.v.’s with negative mean. Set S0=0 and define Sn=X1+⋯+Xn. We propose an importance sampling algorithm to estimate the tail of M=max Sn : 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.