Simulating GI/GI/1 queues and insurance risk processes with subexponential distributions

ABSTRACT

This paper deals with estimating small tail probabilities of the steady-state waiting time in a GI/GI/1 queue with heavy-tailed (subexponential) service times. The problem of estimating infinite horizon ruin probabilities in insurance risk processes with heavy-tailed claims can be transformed into the same framework. It is well-known that naive simulation is ineffective for estimating small probabilities and special fast simulation techniques like importance sampling, multilevel splitting, etc., have to be used. Previous fast simulation techniques for queues with subexponential service times have been confined to M/GI/1 queueing systems. The general approach is to use the Pollaczek-Khintchine transformation to transform the problem into that of estimating the tail distribution of a geometric sum of independent subexponential random variables. However, no such useful transformation exists when one goes from Poisson arrivals to general interarrival-time distributions. We describe an approach that is based on directly simulating the random walk associated with the waiting-time process of the GI/GI/1 queue, using a change of measure called delayed subexponential twisting --- an importance sampling idea recently developed and found useful in the context of M/GI/1 heavy-tailed simulations.

REFERENCES

• 1: Asmussen, S. 1985. Conjugate processes and the simulation of ruin problems. Stochastic Processes and their Applications 20: 213-229.
• 2: Asmussen, S., and K. Binswanger. 1997. Simulation of ruin probabilities for subexponential claims. ASTIN Bulletin 27 (2): 297-318.
• 3: Asmussen, S., K. Binswanger and B. Hojgaard. 1998. Rare event simulation for heavy-tailed distributions. Research Report, Dept. of Mathematical Statistics, Lund University, Box 118, SE-22100 Lund, Sweden.
• 4: Asmussen, S., K. Binswanger and B. Hojgaard. 2000. Rare event simulation for heavy-tailed distributions. Bernoulli 6 (2): 303-322.
• 5: Asmussen, S., and C. Klüppelberg. 1996. Large deviations results for subexponential tails, with applications to insurance risk. Stochastic Processes and their Applications 64: 103-125.
• 6: Boots, N. K., and P. Shahabuddin. 2000. Simulating tail probabilities in GI/GI/1 queues and insurance risk processes with subexponential distributions. Research Report, Dept. of Industrial Engineering and Operations Research, Columbia University, NY 10027.
• 7: Bucklew, J. A. 1990. Large Deviations techniques in decision, simulation, and estimation. John Wiley & Sons, Inc.
• 8: Cheng-Shang Chang , Philip Heidelberger , Sandeep Juneja , Perwez Shahabuddin, Effective bandwidth and fast simulation of ATM intree networks, Performance Evaluation, v.20 n.1-3, p.45-65, May 1994
• 9: Cottrell, M., J. C. Fort and G. Malgouyres. 1983. Large deviations and rare events in the study of stochastic algorithms. IEEE Transactions on Automatic Control AC28: 907-920.
• 10: Chistyakov, V. P. 1964. A theorem on sums of independent positive random variables and its applications to branching processes. Theory of Probability and its Applications 9: 640-648.
• 11: Paul Embrechts , Thomas Mikosch , Claudia Klüppelberg, Modelling extremal events: for insurance and finance, Springer-Verlag, London, 1997
• 12: Embrechts, P., and C. Klüppelberg. 1993. Some aspects of insurance mathematics. Theory of Probability and its Applications 38 (2): 262-295.
• 13: Matthias Falkner , Michael Devetsikiotis , Ioannis Lambadaris, Fast simulation of networks of queues with effective and decoupling bandwidths, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.1, p.45-58, Jan. 1999 [doi>10.1145/301677.301684]
• 14: Frater, M. R., T. M. Lenon and B. D. O Anderson. 1991. Optimally efficient estimation of the statistics of rare events in networks. IEEE Transactions on Automatic Control 36: 1395-1405.
• 15: Anja Feldmann , Ward Whitt, Fitting mixtures of exponentials to long-tail distributions to analyze network performance models, Performance Evaluation, v.31 n.3-4, p.245-279, Jan. 1998 [doi>10.1016/S0166-5316(97)00003-5]
• 16: Feller, W. 1966. An introduction to probability theory and its applications, volume II. John Wiley & Sons, Inc.
• 17: Paul Glasserman , Philip Heidelberger , Perwez Shahabuddin , Tim Zajic, Multilevel Splitting for Estimating Rare Event Probabilities, Operations Research, v.47 n.4, p.585-600, April 1999 [doi>10.1287/opre.47.4.585]
• 18: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 19: Peter W. Glynn , Ward Whitt, The asymptotic efficiency of simulation estimators, Operations Research, v.40 n.3, p.505-520, May–June 1992 [doi>10.1287/opre.40.3.505]
• 20: Goldie, C. M., and S. Resnick. 1988. Distributions that are both subexponential and in the domain of attraction of an extreme-value distribution. Advances in Applied Probability 20: 706-718.
• 21: Juneja, S., and P. Shahabuddin. 1999. Simulating heavy-tailed processes using delayed hazard rate twisting. Research Report, Dept. of Industrial Engineering and Operations Research, Columbia University, NY 10027.
• 22: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 23: Lehtohnen, T., and H. Nyrhinen. 1992. Simulating level-crossing probabilities by importance sampling. Advances in Applied Probability 24: 858-874.
• 24: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 25: Pakes, A. G. 1975. On the tails of waiting time distributions. Journal of Applied Probability 12: 555-564.
• 26: Parekh, S., and J. Walrand 1989. A quick simulation method for excessive backlogs in network of queues. IEEE Transactions on Automatic Control: 54-56.
• 27: Sadowsky, J. S. 1991. Large deviations and efficient estimation of excessive backlogs in GI/G/m queue. IEEE Transactions on Automatic Control 36 (1991): 1383-1394.
• 28: Perwez Shahabuddin, Importance sampling for the simulation of highly reliable Markovian systems, Management Science, v.40 n.3, p.333-352, March 1994 [doi>10.1287/mnsc.40.3.333]
• 29: Siegmund, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. The Annals of Statistics 4: 673-684.