Rare-event simulation of heavy-tailed random walks by sequential importance sampling and resampling. (English) Zbl 1269.65011

Let \({ Y_n}=(y_1,\dots,y_n)\) be the random data and \(\alpha=P({Y_n}\in \Gamma_n)\) be a small probability to be estimated. A Monte Carlo (MC) method using \(m\) simulation runs to estimate \(\alpha\) by \(\hat\alpha_n\) is called \(C_n\) efficient if for any \(\varepsilon>0\) var\((\hat\alpha_n)\leq \varepsilon\alpha_n^2\) for \(m=m_n=O(C_n)\). The authors consider a general MC scheme based on an approximated Doobs \(h\)-transform which carries out importance sampling sequentially within each simulated trajectory and then resamples across all trajectories (SISR). The scheme is applied to the estimation of \({ P}(\sum_{i=1}^n X_i>b)\) and \({ P}(\max_j \sum_{i=1}^j X_i>b)\) for i.i.d. \(X_i\) with heavy tailed distributions. It is shown that SISR provides linearly efficient \(C_n=n\) estimates. Weibull and log-normal distributions are considered as examples.


65C50 Other computational problems in probability (MSC2010)
65C05 Monte Carlo methods
60G50 Sums of independent random variables; random walks
60E05 Probability distributions: general theory
Full Text: DOI Euclid


[1] Asmussen, S. (2003). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 1029.60001
[2] Asmussen, S. and Kroese, D. P. (2006). Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Prob. 38 , 545-558. · Zbl 1097.65017 · doi:10.1239/aap/1151337084
[3] Asmussen, S., Binswanger, K. and Hojgaard, B. (2000). Rare events simulation for heavy-tailed distributions. Bernoulli 6 , 303-322. · Zbl 0958.65010 · doi:10.2307/3318578
[4] Blanchet, J. and Glynn, P. (2008). Efficient rare-event simulation for the maximum of heavy-tailed random walks. Ann. Appl. Prob. 18 , 1351-1378. · Zbl 1147.60315 · doi:10.1214/07-AAP485
[5] Blanchet, J. and Lam, H. (2012). State-dependent importance sampling for rare-event simulation: an overview and recent advances. Surveys Operat. Res. Manag. Sci. 17 , 38-59. · doi:10.1016/j.sorms.2011.09.002
[6] Blanchet, J. and Liu, J. (2006). Efficient simulation for large deviation probabilities of sums of heavy-tailed increments. In Proc. 2006 Winter Simul. Conf. , IEEE, pp. 757-764.
[7] Blanchet, J. H. and Liu, J. (2008). State-dependent importance sampling for regularly varying random walks. Adv. Appl. Prob. 40 , 1104-1128. · Zbl 1159.60022 · doi:10.1239/aap/1231340166
[8] Blanchet, J., Juneja, S. and Rojas-Nandayapa, L. (2008). Efficient tail estimation for sums of correlated lognormals. In Proc. 2008 Winter Simul. Conf. , IEEE, pp. 607-614.
[9] Chan, H. P. and Lai, T. L. (2011). A sequential Monte Carlo approach to computing tail probabilities in stochastic models. Ann. Appl. Prob. 21 , 2315-2342. · Zbl 1246.60042 · doi:10.1214/10-AAP758
[10] Chow, Y. S. and Lai, T. L. (1975). Some one-sided theorems on the tail distribution of sample sums with applications to the last time and largest excess of boundary crossings. Trans. Amer. Math. Soc. 208 , 51-72. · Zbl 0335.60021 · doi:10.2307/1997275
[11] Chow, Y. S. and Lai, T. L. (1978). Paley-type inequalities and convergence rates related to the law of large numbers and extended renewal theory. Z. Wahrscheinlichkeitsth. 45 , 1-19. · Zbl 0397.60030 · doi:10.1007/BF00635960
[12] Chow, Y. S. and Teicher, H. (1988). Probability Theory: Independence, Interchangeability, Martingales , 2nd edn. Springer, New York. · Zbl 0652.60001
[13] Del Moral, P. and Garnier, J. (2005). Genealogical particle analysis of rare events. Ann. Appl. Prob. 15 , 2496-2534. · Zbl 1097.65013 · doi:10.1214/105051605000000566
[14] Dupuis, P., Leder, K. and Wang, H. (2007). Importance sampling for sums of random variables with regularly varying tails. ACM Trans. Model. Comput. Simul. 17 , 21pp. · Zbl 1144.90346
[15] Foss, S., Korshunov, D. and Zachary, S. (2009). An Introduction to Heavy-tailed and Subexponential Distributions . Springer, New York. · Zbl 1250.62025 · doi:10.1007/978-1-4419-9473-8
[16] Juneja, S. (2007). Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error. Queueing Systems 57 , 115-127. · Zbl 1145.90355 · doi:10.1007/s11134-007-9051-8
[17] Kong, A., Liu, J. S. and Wong, W. H. (1994). Sequential imputations and Bayesian missing data problems. J. Amer. Statist. Assoc. 89 , 278-288. · Zbl 0800.62166 · doi:10.2307/2291224
[18] Rozovski\?, L. V. (1989). Probabilities of large deviations of sums of independent random variables with common distribution function in the domain of attraction of the normal law. Theory Prob. Appl. 34 , 625-644. · Zbl 0703.60024 · doi:10.1137/1134080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.