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

By Jose H. Blanchet, Peter W. Glynn. 2008

100 citations recorded by the source corpus.

Let $(X_n:n\geq 0)$ be a sequence of i.i.d. r.v.'s with negative mean. Set $S_0=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\geq 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.

Subfields: Management Science and Operations Research, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/087bc974a9182bd5f34522724b74b76b05e6d9ea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

State-dependent importance sampling for regularly varying random walks (2008, methodology): “Blanchet and Glynn (2007) also introduced the use of Lyapunov inequalities to test the efficiency of SDIS schemes. Blanchet et al. (2007) developed an efficient SDIS algorithm for the tail of the steady-state delay in the G/G/1 queue with regularly varying input. Blanchet et al.’s (2007) algorithm i”
The sample size required in importance sampling (2015, methodology): “A relatively recent technique choosing the proposal distribution, which has been particularly successful in the heavy-tailed setting, is a method based on Lyapunov functions developed by Blanchet and Liu [9, 10], Blanchet and Glynn [7] and Blanchet, Glynn and Leder [8].”