skip to main content
article

Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables

Published: 01 April 2007 Publication History

Abstract

We derive tail asymptotics for the probability that the maximum of sums of a few random variables exceeds an increasing threshold, when the random variables may be light as well as heavy tailed. These probabilities arise in many applications including in PERT networks where our interest may be in measuring the probability of large project delays. We also develop provably asymptotically optimal importance sampling techniques to efficiently estimate these probabilities. In the light-tailed settings we show that an appropriate mixture of exponentially twisted distributions efficiently estimates these probabilities. As is well known, exponential twisting based methods are not applicable in the heavy-tailed settings. To remedy this, we develop techniques that rely on “asymptotic hazard rate twisting” and prove their effectiveness in both light and heavy-tailed settings. We show that in many cases the latter may have implementation advantages over exponential twisting based methods in the light-tailed settings. However, our experiments suggest that when easily implementable, the exponential twisting based methods significantly outperform asymptotic hazard rate twisting based methods.

References

[1]
Adalakha, V. G. and Kulkarni, V. G. 1989. A classified bibliography of research on stochastic PERT networks. INFOR 27, 3, 272--296.
[2]
Crovella, M., Taqqu, M. S., and Bestavros, A. 1998. Heavy tails in the world wide web. In Practical Guide to Heavy Tails, R. Adler, R. Feldman, and M. S. Taqqu, Eds. Birkhauser, Boston, MA 24--31.
[3]
Dembo, A. and Zeitouni, O. 1998. Large Deviations Techniques and Applications, Second ed. Springer, New York, NY.
[4]
Elmaghraby, S. E. 1977. Activity Networks: Project Planning and Control by Network Models. Wiley, New York, NY.
[5]
Embrechts, P., Kluppelberg, C., and Mikosch, T. 1997. Modelling Extremal Events for Insurance and Finance. Springer-Verlag, Berlin, Heidelberg, Germany.
[6]
Feller, W. 1970. An Introduction to Probability Theory and Its Applications, Third ed. Vol. 1. Wiley, New York, NY.
[7]
Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul. 5, 1, 43--85.
[8]
Huang, Z. and Shahabuddin, P. 2004. A unified approach for finite dimensional, rare-event Monte Carlo simulation. In Proceedings of the 2004 Winter Simulation Conference, R. Ignalls, M. Rossetti, J. Smith, and B. Peters, Eds. (Piscataway, NJ). 1616--1624.
[9]
Juneja, S. and Shahabuddin, P. 2002. Simulating heavy-tailed processes using delayed hazard rate twisting. ACM Trans. Model. Comput. Simul. 12, 94--118.
[10]
Juneja, S. and Shahabuddin, P. 2006. Rare event simulation techniques. In Handbook on Simulation, S. Henderson and B. Nelson, Eds. Elsevier, Amsterdam, The Netherlands, 291--350.
[11]
Jureckova, J. 1981. Tail behavior of location estimators. Ann. Stat. 9, 3, 578--585.
[12]
Leland, W. E., Taqqu, M. S., Willinger, W., and Wilson, D. V. 1994. On the self-similar nature of ethernet traffic. IEEE/ACM Trans. Netw. 2, 1--15.
[13]
Pakes, A. G. 2004. Convolution equivalence and infinite divisibility. J. Appl. Prob. 41, 407--424.
[14]
Petrov, V. V. 1975. Sums of Independent Random Variables. Springer-Verlag, New York, NY.
[15]
Pitman, E. J. G. 1980. Subexponential distribution functions. J. Austral. Math. Soc. Ser. A 29, 337--347.
[16]
Sadowsky, J. S. and Bucklew, J. 1990. On large deviation theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theory 36, 3, 579--588.
[17]
Sigman, K. 1999. A primer on heavy-tailed distributions. Queu. Syst. 33, 261--275.

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)Importance Sampling for Minimization of Tail Risks: A TutorialProceedings of the Winter Simulation Conference10.5555/3712729.3712841(1353-1367)Online publication date: 15-Dec-2024
  • (2024)Importance Sampling for Minimization of Tail Risks: A Tutorial2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838883(1353-1367)Online publication date: 15-Dec-2024
  • Show More Cited By

Index Terms

  1. Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables

      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 2
      April 2007
      169 pages
      ISSN:1049-3301
      EISSN:1558-1195
      DOI:10.1145/1225275
      Issue’s Table of Contents

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 01 April 2007
      Published in TOMACS Volume 17, Issue 2

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. PERT networks
      2. importance sampling
      3. rare event simulation
      4. tail asymptotics

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)5
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 16 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)Importance Sampling for Minimization of Tail Risks: A TutorialProceedings of the Winter Simulation Conference10.5555/3712729.3712841(1353-1367)Online publication date: 15-Dec-2024
      • (2024)Importance Sampling for Minimization of Tail Risks: A Tutorial2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838883(1353-1367)Online publication date: 15-Dec-2024
      • (2023)Risk-Sensitive Ordinal OptimizationProceedings of the Winter Simulation Conference10.5555/3643142.3643423(3364-3375)Online publication date: 10-Dec-2023
      • (2023)Importance Sampling for Minimization of Tail Risks: A TutorialProceedings of the Winter Simulation Conference10.5555/3643142.3643261(1433-1447)Online publication date: 10-Dec-2023
      • (2023)Efficient Simulation of Polyhedral Expectations with Applications to FinanceSSRN Electronic Journal10.2139/ssrn.4447428Online publication date: 2023
      • (2023)Importance Sampling for Minimization of Tail Risks: A Tutorial2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10408323(1433-1447)Online publication date: 10-Dec-2023
      • (2023)Risk-Sensitive Ordinal Optimization2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10407133(3364-3375)Online publication date: 10-Dec-2023
      • (2022)Portfolio credit risk with Archimedean copulas: asymptotic analysis and efficient simulationAnnals of Operations Research10.1007/s10479-022-04717-0332:1-3(55-84)Online publication date: 29-Apr-2022
      • (2021)Efficient simulation for linear programming under uncertaintyProceedings of the Winter Simulation Conference10.5555/3522802.3522825(1-12)Online publication date: 13-Dec-2021
      • 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