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

Importance sampling simulation in the presence of heavy tails

Published: 04 December 2005 Publication History

Abstract

We consider importance sampling simulation for estimating rare event probabilities in the presence of heavy-tailed distributions that have polynomial-like tails. In particular, we prove the following negative result: there does not exist an asymptotically optimal state-independent change-of-measure for estimating the probability that a random walk (respectively, queue length for a single server queue) exceeds a "high" threshold before going below zero (respectively, becoming empty). Furthermore, we derive explicit bounds on the best asymptotic variance reduction achieved by importance sampling relative to naïve simulation. We illustrate through a simple numerical example that a "good" state-dependent change-of-measure may be developed based on an approximation of the zero-variance measure.

References

[1]
Ahamed, I., V. S. Borkar, and S. Juneja. 2005. Adaptive importance sampling for markov chains using stochastic approximation. preprint.
[2]
Asmussen, S. 1987. Applied probability and queues. Chichester New York Brisbane Toronto Singapore: John Wiley and Sons.
[3]
Asmussen, S. 1998. Subexponential asymptotics for stochastic processes: extreme behavior, stationary distributions and first passage probabilities. The Annals of Applied Probability 8:354--374.
[4]
Asmussen, S., and K. Binswanger. 1997. Ruin probability simulation for subexponential claims. ASTIN Bull 27:297--318.
[5]
Asmussen, S., K. Binswanger, and B. Hojgaard. 2000. Rare events simulation for heavy-tailed distributions. Bernoulli 6:303--322.
[6]
Asmussen, S., D. P. Kroese, and R. Y. Rubinstein. 2005. Heavy tails, importance sampling and cross-entropy. preprint.
[7]
Bassamboo, A., S. Juneja, and A. Zeevi. 2005. Non-asymptotic optimality of state-independent importance sampling schemes in the presence of heavy tails. OR Letters. To appear.
[8]
Blanchet, J., and P. W. Glynn. 2005. Efficient rare event simulation for the maximum of random walk with heavy-tailed increments. Applied probability conference, Ottawa.
[9]
Boots, N., and P. Shahabuddin. 2001. Simulating tail probabilities in GI/GI/1 queues and insurance risk processes with sub-exponential distributions. In Proceedings of the Winter Simulation Conference, ed. J. A. Joines, R. R. Barton, K. Kang, and P. A. Fishwick, 656--665. Orlando, Florida.
[10]
Embrechts, P., C. Klüppelberg, and T. Mikosch. 1997. Modelling extremal events for insurance and finance. Berlin: Springer-Verlag.
[11]
Glasserman, P. 2003. Monte carlo methods in financial engineering. Springer-Verlag.
[12]
Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Modeling Computer Simulation 5:43--85.
[13]
Juneja, S., and P. Shahabuddin. 2002. Simulating heavy tailed processes using delayed hazard rate twisting. ACM TOMACS 12, 2:94--118.
[14]
Kollman, C., K. Baggerly, D. Cox, and R. Picard. 1999. Adaptive importance sampling on discrete markov chains. The Annals of Applied Probability 9:391--412.
[15]
Resnick, S. 1997. Heavy tail modelling and teletraffic data. Annals of Statistics 25:1805--1869.
[16]
Sadowsky, J. 1991. Large deviations and efficient simulation of excessive backlogs in a GI/G/m queue. IEEE Transactions on Automatic Control 36:1383--1394.
[17]
Siegmund, D. 1985. Sequential Analysis: Tests and confidence intervals. New York: Springer-Verlag.

Cited By

View all
  • (2007)Importance sampling for sums of random variables with regularly varying tailsACM Transactions on Modeling and Computer Simulation10.1145/1243991.124399517:3(14-es)Online publication date: 1-Jul-2007
  • (2006)Efficient simulation for large deviation probabilities of sums of heavy-tailed incrementsProceedings of the 38th conference on Winter simulation10.5555/1218112.1218253(757-764)Online publication date: 3-Dec-2006
  1. Importance sampling simulation in the presence of heavy tails

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WSC '05: Proceedings of the 37th conference on Winter simulation
    December 2005
    2769 pages
    ISBN:0780395190

    Sponsors

    Publisher

    Winter Simulation Conference

    Publication History

    Published: 04 December 2005

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    WSC '05 Paper Acceptance Rate 209 of 316 submissions, 66%;
    Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 16 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2007)Importance sampling for sums of random variables with regularly varying tailsACM Transactions on Modeling and Computer Simulation10.1145/1243991.124399517:3(14-es)Online publication date: 1-Jul-2007
    • (2006)Efficient simulation for large deviation probabilities of sums of heavy-tailed incrementsProceedings of the 38th conference on Winter simulation10.5555/1218112.1218253(757-764)Online publication date: 3-Dec-2006

    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