×

Efficient rare-event simulation for multiple jump events in regularly varying random walks and compound Poisson processes. (English) Zbl 07195280

Summary: We propose a class of strongly efficient rare-event simulation estimators for random walks and compound Poisson processes with a regularly varying increment/jump-size distribution in a general large deviations regime. Our estimator is based on an importance sampling strategy that hinges on a recently established heavy-tailed sample-path large deviations result. The new estimators are straightforward to implement and can be used to systematically evaluate the probability of a wide range of rare events with bounded relative error. They are “universal” in the sense that a single importance sampling scheme applies to a very general class of rare events that arise in heavy-tailed systems. In particular, our estimators can deal with rare events that are caused by multiple big jumps (therefore, beyond the usual principle of a single big jump) as well as multidimensional processes such as the buffer content process of a queueing network. We illustrate the versatility of our approach with several applications that arise in the context of mathematical finance, actuarial science, and queueing theory.

MSC:

65C05 Monte Carlo methods
60F10 Large deviations
60G51 Processes with independent increments; Lévy processes
60G70 Extreme value theory; extremal stochastic processes
60G50 Sums of independent random variables; random walks
60K25 Queueing theory (aspects of probability theory)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] [1] Asmussen S, Glynn P (2007) Stochastic Simulation: Algorithms and Analysis, 1st ed., Stochastic Modelling and Applied Probability, vol. 57. (Springer-Verlag, New York).Crossref, Google Scholar · Zbl 1126.65001 · doi:10.1007/978-0-387-69033-9
[2] [2] Asmussen S, Schmidli H, Schmidt V (1999) Tail probabilities for non-standard risk and queueing processes with subexponential jumps. Adv. Appl. Probab. 31(2):422-447.Crossref, Google Scholar · Zbl 0942.60033 · doi:10.1239/aap/1029955142
[3] [3] Billingsley P (2013) Convergence of Probability Measures, 2nd ed. (John Wiley & Sons, New York).Google Scholar
[4] [4] Blanchet J, Glynn P (2008) Efficient rare-event simulation for the maximum of heavy-tailed random walks. Ann. Appl. Probab. 18(4):1351-1378.Crossref, Google Scholar · Zbl 1147.60315 · doi:10.1214/07-AAP485
[5] [5] Blanchet J, Liu J (2008) State-dependent importance sampling for regularly varying random walks. Adv. Appl. Probab. 40(4):1104-1128.Crossref, Google Scholar · Zbl 1159.60022 · doi:10.1239/aap/1231340166
[6] [6] Blanchet J, Liu J (2010) Efficient importance sampling in ruin problems for multidimensional regularly varying random walks. J. Appl. Probab. 47(2):301-322.Crossref, Google Scholar · Zbl 1257.60001 · doi:10.1239/jap/1276784893
[7] [7] Blanchet J, Glynn P, Liu J (2007) Efficient rare event simulation for heavy-tailed multiserver queues. Technical report, Columbia University, New York.Google Scholar
[8] [8] Blanchet J, Lam H, Tang Q, Yuan Z (2017) Applied robust performance analysis for actuarial applications. Technical report, Columbia University, New York.Google Scholar
[9] [9] Botev ZI, Ridder A, Rojas-Nandayapa L (2016) Semiparametric cross entropy for rare-event simulation. J. Appl. Probab. 53(3):633-649.Crossref, Google Scholar · Zbl 1355.65022 · doi:10.1017/jpr.2016.31
[10] [10] Boxma OJ, Cahen EJ, Koops D, Mandjes M (2018) Linear networks: Rare-event simulation and Markov modulation. Methodology Comput. Appl. Probab., ePub ahead of print June 4, https://doi.org/10.1007/s11009-018-9644-1.Google Scholar
[11] [11] Dębicki K, Mandjes M (2015) Queues and Lévy fluctuation theory, 1st ed., Universitext (Springer International Publishing, Cham, Switzerland).Google Scholar · Zbl 1337.60004
[12] [12] Dupuis P, Wang H (2004) Importance sampling, large deviations, and differential games. Stochastics Stochastic Rep. 76(6):481-508.Crossref, Google Scholar · Zbl 1076.65003 · doi:10.1080/10451120410001733845
[13] [13] Dupuis P, Wang H (2005) On the convergence from discrete to continuous time in an optimal stopping problem. Ann. Appl. Probab. 15(2):1339-1366.Crossref, Google Scholar · Zbl 1138.93066 · doi:10.1214/105051605000000034
[14] [14] Dupuis P, Wang H (2009) Importance sampling for Jackson networks. Queueing Systems 62(1):113-157.Crossref, Google Scholar · Zbl 1166.60329 · doi:10.1007/s11134-009-9124-y
[15] [15] Dupuis P, Leder K, Wang H (2007) Importance sampling for sums of random variables with regularly varying tails. ACM Trans. Model. Comput. Simulation 17(3):Article 14.Crossref, Google Scholar · Zbl 1390.65002 · doi:10.1145/1243991.1243995
[16] [16] Dupuis P, Sezer AD, Wang H (2007) Dynamic importance sampling for queueing networks. Ann. Appl. Probab. 17(4):1306-1346.Crossref, Google Scholar · Zbl 1144.60022 · doi:10.1214/105051607000000122
[17] [17] Embrechts P, Klüppelberg C, Mikosch T (1997) Modelling Extremal Events for Insurance and Finance, 1st ed., Stochastic Modelling and Applied Probability, vol. 33 (Springer-Verlag, Berlin).Crossref, Google Scholar · Zbl 0873.62116 · doi:10.1007/978-3-642-33483-2
[18] [18] Foss S, Korshunov D (2006) Heavy tails in multi-server queue. Queueing Systems Theory Appl. 52(1):31-48.Crossref, Google Scholar · Zbl 1091.60029 · doi:10.1007/s11134-006-3613-z
[19] [19] Foss S, Korshunov D (2012) On large delays in multi-server queues with heavy tails. Math. Oper. Res. 37(2):201-218.Link, Google Scholar · Zbl 1242.90062
[20] [20] Foss S, Korshunov D, Zachary S (2013) An Introduction to Heavy-Tailed and Subexponential Distributions, 2nd ed., Springer Series in Operations Research and Financial Engineering, vol. 38 (Springer-Verlag, New York).Crossref, Google Scholar · Zbl 1274.62005 · doi:10.1007/978-1-4614-7101-1
[21] [21] Glasserman P, Kou SG (1995) Analysis of an importance sampling estimator for tandem queues. ACM Trans. Model. Comput. Simulation 5(1):22-42.Crossref, Google Scholar · Zbl 0841.62083 · doi:10.1145/203091.203093
[22] [22] Glasserman P, Wang Y (1997) Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7(3):731-746.Crossref, Google Scholar · Zbl 0892.60043 · doi:10.1214/aoap/1034801251
[23] [23] Gudmundsson T, Hult H (2014) Markov chain Monte Carlo for computing rare-event probabilities for a heavy-tailed random walk. J. Appl. Probab. 51(2):359-376.Crossref, Google Scholar · Zbl 1291.65014 · doi:10.1239/jap/1402578630
[24] [24] Harrison JM, Reiman MI (1981) Reflected Brownian motion on an orthant. Ann. Probab. 9(2):302-308.Crossref, Google Scholar · Zbl 0462.60073 · doi:10.1214/aop/1176994471
[25] [25] Hu X, Cui H (2010) Generating multi-dimensional discrete distribution random number. Proc. 2010 6th Internat. Conf. Natl. Comput., vol. 3 (IEEE, Piscataway, NJ), 1102-1104.Crossref, Google Scholar · doi:10.1109/ICNC.2010.5583695
[26] [26] Ramasubramanian S (2000) A subsidy-surplus model and the Skorokhod problem in an orthant. Math. Oper. Res. 25(3):509-538.Link, Google Scholar · Zbl 1073.91610
[27] [27] Rhee C-H, Blanchet J, Zwart B (2016) Sample path large deviations for heavy-tailed Lévy processes and random walks. Arxiv preprint arXiv:1606.02795v3.Google Scholar
[28] [28] Skorokhod AV (1961) Stochastic equations for diffusion processes in a bounded region. Theory Probab. Appl. 6(3):264-274.Crossref, Google Scholar · doi:10.1137/1106035
[29] [29] Skorokhod AV (1962) Stochastic equations for diffusion processes in a bounded region, II. Theory Prob. Appl. 7(1):3-23.Crossref, Google Scholar · Zbl 0201.49302 · doi:10.1137/1107002
[30] [30] Tankov P, Cont R (2015) Financial Modelling with Jump Processes, 2nd ed., Chapman and Hall/CRC Financial Mathematics Series (Taylor & Francis, Boca Raton, FL).Google Scholar
[31] [31] Torrisi G (2004) Simulating the ruin probability of risk processes with delay in claim settlement. Stochastic Processes Appl. 112(2):225-244.Crossref, Google Scholar · Zbl 1114.91066 · doi:10.1016/j.spa.2004.02.007
[32] [32] Whitt W (2002) Stochastic-Process Limits, · Zbl 0993.60001 · doi:10.1007/b97479
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.