skip to main content
10.5555/1218112.1218253acmconferencesArticle/Chapter ViewAbstractPublication PageswscConference Proceedingsconference-collections
Article

Efficient simulation for large deviation probabilities of sums of heavy-tailed increments

Published: 03 December 2006 Publication History

Abstract

Let (Xn: n ≥ 0) be a sequence of iid rv's with mean zero and finite variance. We describe an efficient state-dependent importance sampling algorithm for estimating the tail of Sn = X1 + … + Xn in a large deviations framework as n ↗ ∞. Our algorithm can be shown to be strongly efficient basically throughout the whole large deviations region as n ↗ ∞ (in particular, for probabilities of the form P (Sn > kn) as k > 0). The techniques combine results of the theory of large deviations for sums of regularly varying distributions and the basic ideas can be applied to other rare-event simulation problems involving both light and heavy-tailed features.

References

[1]
Asmussen, S., K. Binswanger, and B. Hojgaard. 2000. Rare event simulation for heavy-tailed distributions. Bernoulli 6, Vol. 2, 303--322.
[2]
Asmussen, S., D. P. Kroese. 2006. Improved algorithms for rare event simulation with heavy tails. Advances in Applied Probability 38 (2), to appear.
[3]
Asmussen, S., R. Y. Rubinstein, and C.-L. Wang. 1994. Regenerative Rare Event Simulation via Likelihood Ratios, J. Appl. Prob. 31 (3), 797--815.
[4]
Bassamboo, A., S. Juneja, and A. Zeevi. 2005. Importance sampling simulation in the presence of heavy-tails. Proceedings WSC05.
[5]
Blanchet, J., and P. Glynn. 2006. Efficient Rare-event Simulation for the Maximum of a Random Walk with Heavy-tailed Increments. Preprint.
[6]
Blanchet, J., and P. Glynn. 2006b. Efficient simulation of light-tailed sums: an old-folk song sung to a faster new tune. Preprint.
[7]
Borovkov, A. A. 2000. Estimates for the Distribution of Sums and Maxima of Sums of Random Variables without the Cramer Condition. Siberian Math. J. 41, 811--848.
[8]
Borovkov, A. A., and K. A. Borovkov. 2001. On Probabilities of Large Deviations for Random Walks. I. Regularly Varying Distribution Tails. Theory Prob. Appl. 49, No. 2, 189--205.
[9]
Bucklew, J. 1990. Large Deviation Techniques in Decision, Simulation, and Estimation. John Wiley & Sons, New York.
[10]
Bucklew, J. 2004. Introduction to Rare-event Simulation. Springer, New York.
[11]
Del Moral, P. 2004. Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Probability and its Applications series, Springer.
[12]
Dembo, A., and O. Zeitouni. 1998. Large Deviations Techniques and Applications: Second Edition, Springer-Verlag, New-York.
[13]
Dieker, A. B., and M. Mandjes. 2005. On asymptotically Efficient Simulation of Large Deviation Probabilities. Adv. in Appl. Probab. 37, no. 2, 539--552
[14]
Dupuis, P., K. Leder, and H. Wang. 2006. Importance Sampling for Sums of Random Variables with Regularly Varying Tails. Preprint.
[15]
Dupuis, P., and H. Wang. 2004. Importance Sampling, Large Deviations, and Differential Games. Stochastics and Stochastics Reports 76, 481--508.
[16]
Heidelberger, P. 1995. Fast Simulation of Rare Events in Queueing and Reliability Models, ACM Transactions on Modeling and Computer Simulation, vol.5, no.1 pp. 43--85.
[17]
Juneja, S., and P. Shahabuddin. 2002. Simulating heavytailed processes using delayed hazard rate twisting. ACM TOMACS, 12-2, p. 94--118.
[18]
Meyn, S., and R. Tweedie. 1993. Markov Chains and Stochastic Stability. Springer-Verlag. <http://decision.csl.uiuc.edu/~meyn/pages/book.html>
[19]
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 Probab. Appl., 34, pp. 625--644.
[20]
Sadowsky, J. S. 1996. On Monte Carlo estimation of large deviations probabilities. Ann. Appl. Prob., 6:399--422.
  1. Efficient simulation for large deviation probabilities of sums of heavy-tailed increments

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WSC '06: Proceedings of the 38th conference on Winter simulation
    December 2006
    2429 pages
    ISBN:1424405017

    Sponsors

    • IIE: Institute of Industrial Engineers
    • ASA: American Statistical Association
    • IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
    • IEEE-CS\DATC: The IEEE Computer Society
    • SIGSIM: ACM Special Interest Group on Simulation and Modeling
    • NIST: National Institute of Standards and Technology
    • (SCS): The Society for Modeling and Simulation International
    • INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

    Publisher

    Winter Simulation Conference

    Publication History

    Published: 03 December 2006

    Check for updates

    Qualifiers

    • Article

    Conference

    WSC06
    Sponsor:
    • IIE
    • ASA
    • IEICE ESS
    • IEEE-CS\DATC
    • SIGSIM
    • NIST
    • (SCS)
    • INFORMS-CS
    WSC06: Winter Simulation Conference 2006
    December 3 - 6, 2006
    California, Monterey

    Acceptance Rates

    WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;
    Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 150
      Total Downloads
    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media