publication . Article . Other literature type . Preprint . 2008

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

Blanchet, Jose; Glynn, Peter;
Open Access
  • Published: 01 Aug 2008 Journal: The Annals of Applied Probability, volume 18, pages 1,351-1,378 (issn: 1050-5164, Copyright policy)
  • Publisher: Institute of Mathematical Statistics
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 Si...
free text keywords: Statistics, Probability and Uncertainty, Statistics and Probability, Mathematical optimization, Independent and identically distributed random variables, Relative standard deviation, Estimator, Coefficient of variation, Importance sampling, Rare event simulation, Random variable, Combinatorics, Random walk, Mathematics, State-dependent importance sampling, rare-event simulation, heavy-tails, Lyapunov bounds, random walks, single-server queue, change-of-measure, 60G50, 60J05, 68W40, 60G70, 60J20, Mathematics - Probability, 60G50, 60J05, 68W40 (Primary) 60G70, 60J20 (Secondary)

P (X ≤ s)P (X > t − s) ds Adler, J., Feldman, R. and Taqqu, M., eds. (1998). A Practical Guide to Heavy Tails: Statistical Techniques and Applications. Birkh¨auser, Boston. MR1652283 Asmussen, S. (2003). Applied Probability and Queues. Springer, New York. MR1978607 Asmussen, S. and Glynn, P. (2007). Stochastic Simulation: Algorithms and Analysis. Springer, New York. MR2331321

Asmussen, S. and Binswanger, K. (1997). Simulation of ruin probabilities for subexponential claims. Ast. Bulletin 27 297-318. [OpenAIRE]

Asmussen, S., Binswanger, K. and Hojgaard, B. (2000). Rare event simulation for heavy-tailed distributions. Bernoulli 6 303-322. MR1748723 Asmussen, S. and Kluppelberg, C. (1996). Large deviation results for subexponential tails, with applications to insurance risk. Stoch. Proc. Appl. 64 103-125. MR1419495 Asmussen, S. and Kroese, D. (2006). Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Probab. 38 545-558. MR2264957 Bassamboo, A., Juneja, S. and Zeevi, A. (2006). On the efficiency loss of stateindependent importance sampling in the presence of heavy-tails. Oper. Res. Lett. 34 521-531. [OpenAIRE]

Blanchet, J., Glynn, P. and Liu, J. C. (2007). Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue. QUESTA 57 99-113.

Blanchet, J. and Li, C. (2006). Efficient rare-event simulation for geometric sums. Proc. RESIM, Bamberg. Germany.

Borovkov, A. A. and Borovkov, K. A. (2001). On probabilities of large deviations for random walks. I: Regularly varying distribution tails. Theory Probab. Appl. 49 189-205. [OpenAIRE]

Bucklew, J. (2004). Introduction to Rare-Event Simulation. Springer, New York. MR2045385

Dupuis, P. and Wang, H. (2004). Importance sampling, large deviations, and differential games. Stochastics Stochastics Rep. 76 481-508. MR2100018 Dupuis, P., Leder, K. and Wang, H. (2006). Importance sampling for sums of random variables with regularly varying tails. TOMACS 17.

Embrechts, P., Klu¨ppelberg, C. and Mikosch, T. (1997). Modelling Extremal Events for Insurance and Finance. Springer, New York. MR1458613 Hammersley, J. and Morton, K. (1954). Poor man's Monte Carlo. J. Roy. Statist. Soc. Ser. B 16 23-38. MR0064475

Juneja, S. and Shahabuddin, P. (2002). Simulating heavy-tailed processes using delayed hazard rate twisting. ACM TOMACS 12 94-118. [OpenAIRE]

Juneja, S. and Shahabuddin, P. (2006). Rare event simulation techniques: An introduction and recent advances. In Handbook on Simulation (S. Henderson and B. Nelson, eds.) 291-350. North-Holland, Amsterdam. [OpenAIRE]

Liu, J. (2001). Monte Carlo Strategies in Scientific Computing. Springer, New York. MR1842342

Meyn, S. and Tweedie, R. (1993). Markov Chains and Stochastic Stability. Available at˜meyn/pages/book.html. MR1287609 Rosenbluth, M. and Rosenbluth, A. (1955). Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23 356-359. [OpenAIRE]

Siegmund, D. (1976). Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4 673-684. MR0418369 [OpenAIRE]

Department of Management Science and Engineering Stanford University Stanford, California 94305 USA

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue