Efficient rare-event simulation for the maximum of heavy-tailed random walks

• 成果类型: Article
• 署名作者: Blanchet, Jose; Glynn, Peter
• 署名单位: Harvard University; Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/07-AAP485
• 发表日期: 2008
• 页码: 1351-1378
• 关键词: monte-carlo

摘要

Let (X : n >_ 0) be a sequence of i.i.d. r.v.'s with negative mean. Set So = 0 and define Sn = XI + - - - + Xn. We propose an importance sampling algorithm to estimate the tail of M = max{S : n > Ol 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.