skip to main content
article

Importance sampling for sums of random variables with regularly varying tails

Published: 01 July 2007 Publication History

Abstract

Importance sampling is a variance reduction technique for efficient estimation of rare-event probabilities by Monte Carlo. For random variables with heavy tails there is little consensus on how to choose the change of measure used in importance sampling. In this article we study dynamic importance sampling schemes for sums of independent and identically distributed random variables with regularly varying tails. The number of summands can be random but must be independent of the summands. For estimating the probability that the sum exceeds a given threshold, we explicitly identify a class of dynamic importance sampling algorithms with bounded relative errors. In fact, these schemes are nearly asymptotically optimal in the sense that the second moment of the corresponding importance sampling estimator can be made as close as desired to the minimal possible value.

References

[1]
Asmussen, S. 2000. Ruin Probabilities. World Scientific, Singapore.
[2]
Asmussen, S. and Kroese, D. 2004. Improved algorithms for rare event simulation with heavy tails. Tech. rep., The Danish National Research Foundation: Network in Mathematical Physics and Stochastics.
[3]
Bassamboo, A., Juneja, S., and Zeevi, A. 2005. Importance sampling simulation in the presence of heavy tails. In Proceedings of the 2005 Winter Simulation Conference, F. Armstrong, J. Joines, M. Kuhl, and N. Steiger, Eds.
[4]
Billingsley, P. 1968. Convergence of Probability Measures. John Wiley, New York.
[5]
Bingham, N., Goldie, C., and Teugels, J. 1987. Regular Variation. Cambridge University Press, Cambridge.
[6]
Crovella, M., Taqqu, M., and Bestavros, A. 1998. Heavy-tailed probability distributions in the World Wide Web. In A Practical Guide to Heavy Tails, R. Adler, R. Feldman, and M. Taqqu, Eds. Birkhauser, Boston, 3--26.
[7]
Dupuis, P. and Ellis., R. S. 1997. A Weak Convergence Approach to the Theory of Large Deviations. John Wiley & Sons, New York.
[8]
Dupuis, P. and Wang, H. 2004. Importance sampling, large deviations, and differential games. Stochastics and Stochastics Reports 76, 481--508.
[9]
Dupuis, P. and Wang, H. 2005. Dynamic importance sampling for uniformly recurrent Markov chains. Annals of Applied Probability 15, 1--38.
[10]
Embrechts, P., Kluppelberg, C., and Mikosch, T. 1997. Modelling Extremal Events. Springer, Berlin.
[11]
Juneja, S. and Shahabuddin, P. 2002. Simulating heavy tailed processes using delayed hazard rate twisting. ACM Trans. Model. Comput. Simul. 12, 94--118.
[12]
Willinger, W., Taqqu, M., Sherman, R., and Wilson, D. 1997. Self-similarity through high-variability: Statistical analysis of ethernet LAN traffic at the source level. IEEE/ACM Trans. Netw. 5, 71--86.

Cited By

View all
  • (2025)Achieving Efficiency in Black-Box Simulation of Distribution Tails with Self-Structuring Importance SamplersOperations Research10.1287/opre.2021.033173:1(325-343)Online publication date: 1-Jan-2025
  • (2024)An importance sampling for a function of a multivariate random variableCommunications for Statistical Applications and Methods10.29220/CSAM.2024.31.1.06531:1(65-85)Online publication date: 31-Jan-2024
  • (2023)Importance Sampling Strategy for Heavy-Tailed Systems with Catastrophe PrincipleProceedings of the Winter Simulation Conference10.5555/3643142.3643148(76-90)Online publication date: 10-Dec-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation
ACM Transactions on Modeling and Computer Simulation  Volume 17, Issue 3
July 2007
104 pages
ISSN:1049-3301
EISSN:1558-1195
DOI:10.1145/1243991
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2007
Published in TOMACS Volume 17, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Dynamic importance sampling
  2. asymptotically optimal relative error
  3. bounded relative error
  4. rare events
  5. regularly varying tails
  6. variance reduction

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2025)Achieving Efficiency in Black-Box Simulation of Distribution Tails with Self-Structuring Importance SamplersOperations Research10.1287/opre.2021.033173:1(325-343)Online publication date: 1-Jan-2025
  • (2024)An importance sampling for a function of a multivariate random variableCommunications for Statistical Applications and Methods10.29220/CSAM.2024.31.1.06531:1(65-85)Online publication date: 31-Jan-2024
  • (2023)Importance Sampling Strategy for Heavy-Tailed Systems with Catastrophe PrincipleProceedings of the Winter Simulation Conference10.5555/3643142.3643148(76-90)Online publication date: 10-Dec-2023
  • (2023)Importance Sampling Strategy for Heavy-Tailed Systems with Catastrophe Principle2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10407503(76-90)Online publication date: 10-Dec-2023
  • (2023)State-dependent importance sampling for estimating expectations of functionals of sums of independent random variablesStatistics and Computing10.1007/s11222-022-10202-233:2Online publication date: 4-Feb-2023
  • (2022)Replicated Computational Results (RCR) Report for “A New Test for Hamming-Weight Dependencies”ACM Transactions on Modeling and Computer Simulation10.1145/352758332:3(1-3)Online publication date: 6-Jul-2022
  • (2022)A New Test for Hamming-Weight DependenciesACM Transactions on Modeling and Computer Simulation10.1145/352758232:3(1-13)Online publication date: 25-Jul-2022
  • (2022)EMPRESS: Accelerating Scientific Discovery through Descriptive Metadata ManagementACM Transactions on Storage10.1145/352369818:4(1-49)Online publication date: 12-Dec-2022
  • (2022)Rare-event Simulation for Neural Network and Random Forest PredictorsACM Transactions on Modeling and Computer Simulation10.1145/351938532:3(1-33)Online publication date: 6-Jul-2022
  • (2022)Bayesian Optimisation vs. Input Uncertainty ReductionACM Transactions on Modeling and Computer Simulation10.1145/351038032:3(1-26)Online publication date: 25-Jul-2022
  • Show More Cited By

View Options

Login options

Full Access

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