Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T09:06:40.521Z Has data issue: false hasContentIssue false
  • English
  • Français

State-dependent importance sampling for regularly varying random walks

Part of: Stochastic processes Markov processes Algorithms - Computer Science

Published online by Cambridge University Press:  01 July 2016

Jose H. Blanchet  and
Jingchen Liu
Jose H. Blanchet*
Affiliation:
Columbia University
Jingchen Liu*
Affiliation:
Columbia University
*
∗ Postal address: Department of Industrial Engineering and Operations Research, Columbia University, S. W. Mudd Building, 500 West 120th Street, New York, NY 10027-6699. Email address: blanchet@fas.harvard.edu
∗∗ Postal address: Department of Statistics, Columbia University, 1255 Amsterdam Avenue, Room 1030, New York, NY 10027.
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.

Consider a sequence (X k : k ≥ 0) of regularly varying independent and identically distributed random variables with mean 0 and finite variance. We develop efficient rare-event simulation methodology associated with large deviation probabilities for the random walk (S n : n ≥ 0). Our techniques are illustrated by examples, including large deviations for the empirical mean and path-dependent events. In particular, we describe two efficient state-dependent importance sampling algorithms for estimating the tail of S n in a large deviation regime as n ↗ ∞. The first algorithm takes advantage of large deviation approximations that are used to mimic the zero-variance change of measure. The second algorithm uses a parametric family of changes of measure based on mixtures. Lyapunov-type inequalities are used to appropriately select the mixture parameters in order to guarantee bounded relative error (or efficiency) of the estimator. The second example involves a path-dependent event related to a so-called knock-in financial option under heavy-tailed log returns. Again, the importance sampling algorithm is based on a parametric family of mixtures which is selected using Lyapunov bounds. In addition to the theoretical analysis of the algorithms, numerical experiments are provided in order to test their empirical performance.

Keywords

State dependentimportance samplingregularly varyingrandom walkheavy tailstrong efficiencyrare-event simulation

MSC classification

Primary: 60G50: Sums of independent random variables; random walks 60J05: Discrete-time Markov processes on general state spaces 68W40: Analysis of algorithms
Secondary: 60G70: Extreme value theory; extremal processes

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 40 , Issue 4 , December 2008 , pp. 1104 - 1128
Copyright
Copyright © Applied Probability Trust 2008 

References

Adler, J., Feldman, R. and Taqqu, M. (eds) (1998). A Practical Guide to Heavy Tails: Statistical Techniques and Applications. Birkhäuser, Boston, MA.Google Scholar
Anantharam, V. (1989). How large delays build up in a GI/G/1 queue. Queueing Systems 5, 345–367.Google Scholar
Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
Asmussen, S. and Glynn, P. (2007). Stochastic Simulation: Algorithms and Analysis. Springer, New York.Google Scholar
Asmussen, S. and Kroese, D. P. (2006). Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Prob. 38, 545–558.Google Scholar
Asmussen, S., Binswanger, K. and Højgaard, B. (2000). Rare event simulation for heavy-tailed distributions. Bernoulli 6, 303–322.Google Scholar
Bassamboo, A., Juneja, S. and Zeevi, A. (2005). Importance sampling simulation in the presence of heavy tails. In Proc. 37th Conf. Winter Simulation (December 2005), IEEE, pp. 664–672.Google Scholar
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
Blanchet, J. and Liu, J. C. (2006). Efficient simulation for large deviation probabilities of sums of heavy-tailed increments. In Proc. 38th Conf. Winter Simulation (December 2006), IEEE, pp. 757–764.Google Scholar
Blanchet, J. and Liu, J. C. (2007). Path-sampling for state-dependent importance sampling. In Proc. 39th Conf. Winter Simulation (December 2007), IEEE, pp. 380–388.Google Scholar
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. Queueing Systems 57, 99–113.Google Scholar
Blanchet, J., Glynn, P. and Liu, J. C. (2008). Efficient rare event simulation for heavy-tailed multiserver queues. Department of Statistics, Columbia University.Google Scholar
Borovkov, A. A. and Borovkov, K. A. (2001). On large deviations of probabilities for random walks. I. Regularly varying distribution tails. Theory Prob. Appl. 49, 193–213.Google Scholar
Bucklew, J. (2004). Introduction to Rare Event Simulation. Springer, New York.Google Scholar
Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd edn. Springer, New York.Google Scholar
Donsker, M. and Varadhan, S. (1975). Asymptotic evaluation of certain Markov process expectations for large time. I. II. Commun. Pure Appl. Math. 28, 1–47.Google Scholar
Dupuis, P. and Wang, H. (2004). Importance sampling, large deviations, and differential games. Stoch. Stoch. Reports 76, 481–508.Google Scholar
Dupuis, P. and Wang, H. (2005). On the convergence from discrete to continuous time in an optimal stopping problem. Ann. Appl. Prob. 15, 1339–1366.Google Scholar
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, 1–21.Google Scholar
Foss, S. and Korshunov, D. (2006). Heavy tails in multi-server queues. Queueing Systems 52, 31–48.Google Scholar
Foss, S., Konstantopoulos, T. and Zachary, S. (2007). Discrete and continuous time modulated random walks with heavy-tailed increments. J. Theoret. Prob. 20, 581–612.Google Scholar
Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering (Appl. Math. 53). Springer. New York.Google Scholar
Glasserman, P. and Kou, S. (1995). Analysis of an importance sampling estimator for tandem queues. ACM Trans. Model. Comput. Simul. 4, 22–42.Google Scholar
Glasserman, P. and Wang, Y. (1997). Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Prob. 7, 731–746.Google Scholar
Hult, H. and Lindskog, F. (2005). Extremal behavior for regularly varying stochastic processes. Stoch. Process. Appl. 115, 249–274.Google Scholar
Hult, H., Lindskog, F., Mikosch, T. and Samorodnitsky, G. (2005). Functional large deviations for multivariate regularly random walks. Ann. Appl. Prob. 15, 2651–2680.Google Scholar
Juneja, S. and Shahabuddin, P. (2002). Simulating heavy tailed processes using delayed hazard rate twisting. ACM Trans. Model. Comput. Simul. 12, 94–118.CrossRefGoogle Scholar
Juneja, S. and Shahabuddin, P. (2006). Rare event simulation techniques: introduction and recent advances. In Handbook on Simulation, eds Henderson, S. and Nelson, B., North-Holland, Amsterdam, pp. 291–350.Google Scholar
Nagaev, A. V. (1969a). Integral limit theorems for large deviations when Cramér's condition is not fulfilled. I. Theory Prob. Appl. 14, 51–64.Google Scholar
Nagaev, A. V. (1969b). Integral limit theorems for large deviations when Cramér's condition is not satisfied. II. Theory Prob. Appl. 14, 193–208.Google Scholar
Resnick, S. (1987). Extreme Values, Regular Variation, and Point Processes (Appl. Prob. 4). Springer, New York.Google Scholar
Rozovskii, 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.Google Scholar
Sadowsky, J. S. and Bucklew, J. (1990). On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theory 36, 579–588.Google Scholar
Zwart, A. (2001). Queueing systems with heavy tails. Doctoral Thesis, Technische Universiteit Eindhoven.Google Scholar