Hostname: page-component-6898cfcb55-kwdml Total loading time: 0 Render date: 2026-11-11T11:49:57.916Z Has data issue: false hasContentIssue false
  • English
  • Français

Importance sampling of heavy-tailed iterated random functions

Part of:Probabilistic methods, simulation and stochastic differential equationsMarkov processes

Published online by Cambridge University Press:  16 November 2018

Bohan Chen,
Chang-Han Rhee and
Bert Zwart
Bohan Chen*
Affiliation:
Centrum Wiskunde & Informatica
Chang-Han Rhee*
Affiliation:
Centrum Wiskunde & Informatica
Bert Zwart*
Affiliation:
Centrum Wiskunde & Informatica
*
* Postal address: Stochastics Group, Centrum Wiskunde & Informatica, Science Park 123, 1098 XG, Amsterdam, The Netherlands.
*** Current address: Industrial Engineering and Management Sciences, 2145 Sheridan Road, Tech C150, Evanston, Illinois, IL 60208-3109, USA. Email address: chang-han.rhee@northwestern.edu
* Postal address: Stochastics Group, Centrum Wiskunde & Informatica, Science Park 123, 1098 XG, Amsterdam, The Netherlands.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the stationary solution Z of the Markov chain {Zn}n∈ℕ defined by Zn+1=ψn+1(Zn), where {ψn}n∈ℕ is a sequence of independent and identically distributed random Lipschitz functions. We estimate the probability of the event {Z>x} when x is large, and develop a state-dependent importance sampling estimator under a set of assumptions on ψn such that, for large x, the event {Z>x} is governed by a single large jump. Under natural conditions, we show that our estimator is strongly efficient. Special attention is paid to a class of perpetuities with heavy tails.

Keywords

State-dependent importance samplingheavy-tailed distributioniterated random functionperpetuities

MSC classification

Primary:65C05: Monte Carlo methods
Secondary:60J05: Discrete-time Markov processes on general state spaces

Information

Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 3 , September 2018, pp. 805 - 832
Copyright
Copyright © Applied Probability Trust 2018 

References

[1]Asmussen, S. (2003). Applied Probability and Queues. Springer, New York.Google Scholar
[2]Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis. Springer, New York.Google Scholar
[3]Asmussen, S. and Nielsen, H. M. (1995). Ruin probabilities via local adjustment coefficients. J. Appl. Prob. 32, 736–755.Google Scholar
[4]Asmussen, S., Schmidli, H. and Schmidt, V. (1999). Tail probabilities for non-standard risk and queueing processes with subexponential jumps. Adv. Appl. Prob. 31, 422–447.Google Scholar
[5]Blanchet, J. and Glynn, P. (2008). Efficient rare-event simulation for the maximum of heavy-tailed random walks. Ann. Appl. Prob. 18, 1351–1378.Google Scholar
[6]Blanchet, J., Lam, H. and Zwart, B. (2012). Efficient rare-event simulation for perpetuities. Stoch. Process. Appl. 122, 3361–3392.Google Scholar
[7]Blanchet, J. and Zwart, B. (2007). Importance sampling of compounding processes. In Proc. 2007 Winter Simulation Conference, IEEE, pp. 372–379.Google Scholar
[8]Buraczewski, D., Damek, E. and Mikosch, T. (2016). Stochastic Models with Power-Law Tails: The Equation X=AX+B. Springer, Cham.Google Scholar
[9]Collamore, J. F. and Vidyashankar, A. N. (2013). Tail estimates for stochastic fixed point equations via nonlinear renewal theory. Stoch. Process. Appl. 123, 3378–3429.Google Scholar
[10]Collamore, J. F., Diao, G. and Vidyashankar, A. N. (2014). Rare event simulation for processes generated via stochastic fixed point equations. Ann. Appl. Prob. 24, 2143–2175.Google Scholar
[11]Douc, R., Moulines, E. and Soulier, P. (2007). Computable convergence rates for sub-geometric ergodic Markov chains. Bernoulli 13, 831–848.Google Scholar
[12]Dyszewski, P. (2016). Iterated random functions and slowly varying tails. Stoch. Process. Appl. 126, 392–413.Google Scholar
[13]Embrechts, P., Klüppelberg, C. and Mikosch, T. (1997). Modelling Extremal Events: For Insurance and Finance. Springer, Berlin.Google Scholar
[14]Foss, S., Korshunov, D. and Zachary, S. (2013). An Introduction to Heavy-Tailed and Subexponential Distributions, 2nd edn. Springer, New York.Google Scholar
[15]Ganesh, A., O'Connell, N. and Wischik, D. (2004). Big Queues. Springer, Berlin.Google Scholar
[16]Goldie, C. M. (1991). Implicit renewal theory and tails of solutions of random equations. Ann. Appl. Prob. 1, 126–166.Google Scholar
[17]Goldie, C. M. and Grübel, R. (1996). Perpetuities with thin tails. Adv. Appl. Prob. 28, 463–480.Google Scholar
[18]Grey, D. R. (1994). Regular variation in the tail behaviour of solutions of random difference equations. Ann. Appl. Prob. 4, 169–183.Google Scholar
[19]Grincevičius, A. K. (1975). Limit theorems for products of random linear transformations on the line. Lithuanian Math. J. 15, 568–579.Google Scholar
[20]Jarner, S. F. and Roberts, G. O. (2002). Polynomial convergence rates of Markov chains. Ann. Appl. Prob. 12, 224–247.Google Scholar
[21]Kalashnikov, V. and Tsitsiashvili, G. (1999). Tails of waiting times and their bounds. Queueing Systems Theory Appl. 32, 257–283.Google Scholar
[22]Kesten, H. (1973). Random difference equations and renewal theory for products of random matrices. Acta Math. 131, 207–248.Google Scholar
[23]Klüppelberg, C. (1988). Subexponential distributions and integrated tails. J. Appl. Prob. 25, 132–141.Google Scholar
[24]Maulik, K. and Zwart, B. (2006). Tail asymptotics for exponential functionals of Lévy processes. Stoch. Process. Appl. 116, 156–177.Google Scholar
[25]Mirek, M. (2011). Heavy tail phenomenon and convergence to stable laws for iterated Lipschitz maps. Prob. Theory Relat. Fields 151, 705–734.Google Scholar
[26]Pakes, A. G. (1975). On the tails of waiting-time distributions. J. Appl. Prob. 12, 555–564.Google Scholar
[27]Palmowski, Z. and Zwart, B. (2007). Tail asymptotics of the supremum of a regenerative process. J. Appl. Prob. 44, 349–365.Google Scholar
[28]Rhee, C.-H. and Glynn, P. W. (2015). Unbiased estimation with square root convergence for SDE models. Operat. Res. 63, 1026–1043.Google Scholar
[29]Veraverbeke, N. (1977). Asymptotic behaviour of Wiener-Hopf factors of a random walk. Stoch. Process. Appl. 5, 27–37.Google Scholar
[30]Vervaat, W. (1979). On a stochastic difference equation and a representation of nonnegative infinitely divisible random variables. Adv. Appl. Prob. 11, 750–783.Google Scholar
[31]Zachary, S. (2004). A note on Veraverbeke's theorem. Queueing Systems 46, 9–14.Google Scholar