Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error. (English) Zbl 1145.90355

Summary: Efficient estimation of tail probabilities involving heavy tailed random variables is amongst the most challenging problems in Monte-Carlo simulation. In the last few years, applied probabilists have achieved considerable success in developing efficient algorithms for some such simple but fundamental tail probabilities. Usually, unbiased importance sampling estimators of such tail probabilities are developed and it is proved that these estimators are asymptotically efficient or even possess the desirable bounded relative error property. In this paper, as an illustration, we consider a simple tail probability involving geometric sums of heavy tailed random variables. This is useful in estimating the probability of large delays in \(M/G/1\) queues. In this setting we develop an unbiased estimator whose relative error decreases to zero asymptotically. The key idea is to decompose the probability of interest into a known dominant component and an unknown small component. Simulation then focuses on estimating the latter ‘residual’ probability. Here we show that the existing conditioning methods or importance sampling methods are not effective in estimating the residual probability while an appropriate combination of the two estimates it with bounded relative error. As a further illustration of the proposed ideas, we apply them to develop an estimator for the probability of large delays in stochastic activity networks that has an asymptotically zero relative error.


90B22 Queues and service in operations research
Full Text: DOI


[1] Adalakha, V.G., Kulkarni, V.G.: A classified bibliography of research on stochastic PERT networks. INFOR 27(3), 272–296 (1989) · Zbl 0678.90033
[2] Asmussen, S.: Ruin Probabilities. World Scientific, London (2000) · Zbl 0960.60003
[3] Asmussen, S.: Applied Probabilities and Queues, 2nd edn. Springer, New York (2003) · Zbl 1029.60001
[4] Asmussen, S., Binswanger, K.: Simulation of ruin probabilities for subexponential claims. ASTIN Bull. 27(2), 297–318 (1997) · doi:10.2143/AST.27.2.542054
[5] Asmussen, S., Kroese, D.P.: Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Probab. 38(2), 545–558 (2006) · Zbl 1097.65017 · doi:10.1239/aap/1151337084
[6] Asmussen, S., Binswanger, K., Hojgaard, B.: Rare event simulation for heavy tailed distributions. Bernoulli 6(2), 303–322 (2000) · Zbl 0958.65010 · doi:10.2307/3318578
[7] Blanchet, J., Liu, J.: Efficient simulation for large deviation probabilities of sums of heavy-tailed random variables, In: Proceedings of the 2006 WSC Conference, pp. 757–764, 2006
[8] Dupuis, P., Leder, K., Wang, H.: Importance sampling for sums of random variables with regularly varying tails. ACM Trans. Modell. Simul. 17, 3 (2007) · Zbl 1281.65004 · doi:10.1145/1189756.1189759
[9] Elmaghraby, S.E.: Activity Networks: Project Planning and Control by Network Models. Wiley, New York (1977) · Zbl 0385.90076
[10] Embrechts, P., Kluppelberg, C., Mikosch, T.: Modelling Extremal Events for Insurance and Finance. Springer, Berlin (1997) · Zbl 0873.62116
[11] Glasserman, P.: Monte Carlo Methods in Financial Engineering. Springer, New York (2004) · Zbl 1038.91045
[12] Feller, W.: An Introduction to Probability Theory and Its Applications, vol. II. Wiley, New York (1971) · Zbl 0219.60003
[13] Hartinger, J., Kortschak, D.: On the efficiency of Asmussen-Kroese-estimator and its applications to stop-loss transforms. In: Proceedings of RESIM 2006 Conference held in Bamberg, Germany, 2006 · Zbl 1182.91092
[14] Juneja, S., Shahabuddin, P.: Simulating heavy tailed processes using delayed hazard rate twisting. ACM Trans. Modell. Simul. 12, 94–118 (2002) · doi:10.1145/566392.566394
[15] Juneja, S., Shahabuddin, P.: Rare-event simulation techniques: an introduction and recent advances. In: Henderson, S.G., Nelson, B.L. (eds.) Handbook in OR & MS, vol. 13, pp. 291–350. Elsevier, Amsterdam (2006)
[16] Juneja, S., Karandikar, R.L., Shahabuddin, P.: Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables. ACM Trans. Modell. Simul. 17(2), 7 (2007) · doi:10.1145/1225275.1225278
[17] Omey, E.: On the difference between the product and the convolution product of distribution functions. Publ. Inst. Math. 55(69), 111–145 (1994) · Zbl 0824.60032
[18] Omey, E.: On the difference between the distribution function of the sum and the maximum of real random variables. Publ. Inst. Math. 71(85), 63–77 (2002) · Zbl 1029.60012 · doi:10.2298/PIM0271063O
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.