×

On the generalization of the hazard rate twisting-based simulation approach. (English) Zbl 1384.65013

Summary: Estimating the probability that a sum of random variables (RVs) exceeds a given threshold is a well-known challenging problem. A naive Monte Carlo simulation is the standard technique for the estimation of this type of probability. However, this approach is computationally expensive, especially when dealing with rare events. An alternative approach is represented by the use of variance reduction techniques, known for their efficiency in requiring less computations for achieving the same accuracy requirement. Most of these methods have thus far been proposed to deal with specific settings under which the RVs belong to particular classes of distributions. In this paper, we propose a generalization of the well-known hazard rate twisting Importance Sampling-based approach that presents the advantage of being logarithmic efficient for arbitrary sums of RVs. The wide scope of applicability of the proposed method is mainly due to our particular way of selecting the twisting parameter. It is worth observing that this interesting feature is rarely satisfied by variance reduction algorithms whose performances were only proven under some restrictive assumptions. It comes along with a good efficiency, illustrated by some selected simulation results comparing the performance of the proposed method with some existing techniques.

MSC:

65C50 Other computational problems in probability (MSC2010)
60F10 Large deviations
60G50 Sums of independent random variables; random walks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, I.O., Marshall, W.: Life Distributions: Structure of Nonparametric, Semiparametric, and Parametric Familie. Springer, New York (2007) · Zbl 1304.62019
[2] Asmussen, S., Glynn, P.W.: Stochastic Simulation : Algorithms and Analysis. Stochastic Modelling and Applied Probability. Springer, New York (2007) · Zbl 1126.65001
[3] 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.1017/S0001867800001099
[4] Asmussen, S., Kortschak, D.: Error rates and improved algorithms for rare event simulation with heavy Weibull tails. Methodol. Comput. Appl. Probab. 17(2), 441-461 (2015) · Zbl 1347.60029 · doi:10.1007/s11009-013-9371-6
[5] Asmussen, S., Blanchet, J.H., Juneja, S., Rojas-Nandayapa, L.: Efficient simulation of tail probabilities of sums of correlated Lognormals. Ann. OR 189(1), 5-23 (2011) · Zbl 1279.60027 · doi:10.1007/s10479-009-0658-5
[6] Babich, F., Lombardi, G.: Statistical analysis and characterization of the indoor propagation channel. IEEE Trans. Commun. 48(3), 455-464 (2000) · doi:10.1109/26.837048
[7] Beaulieu, N.C., Rajwani, F.: Highly accurate simple closed-form approximations to Lognormal sum distributions and densities. IEEE Commun. Lett. 8(12), 709-711 (2004) · doi:10.1109/LCOMM.2004.837657
[8] Beaulieu, N.C., Xie, Q.: An optimal Lognormal approximation to Lognormal sum distributions. IEEE Trans. Veh. Technol. 53(2), 479-489 (2004) · doi:10.1109/TVT.2004.823494
[9] Ben Letaief, K.: Performance analysis of digital lightwave systems using efficient computer simulation techniques. IEEE Trans. Commun. 43(234), 240-251 (1995) · Zbl 0983.94501 · doi:10.1109/26.380042
[10] Ben Rached, N., Benkhelifa, F., Alouini, M.-S., Tempone, R.: A fast simulation method for the Log-normal sum distribution using a hazard rate twisting technique. In: Proceedings of the IEEE International Conference on Communications (ICC’2015), London (2015a)
[11] Ben Rached, N., Kammoun, A., Alouini, M.-S., Tempone, R.: An improved hazard rate twisting approach for the statistic of the sum of subexponential variates. IEEE Commun. Lett. 19(1), 14-17 (2015b) · doi:10.1109/LCOMM.2014.2368562
[12] Blanchet, J., Liu, J.C.: State-dependent importance sampling for regularly varying random walks. Adv. Appl. Probab. 40(4), 1104-1128 (2008) · Zbl 1159.60022 · doi:10.1017/S0001867800002986
[13] Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[14] Bucklew, J.A.: Introduction to Rare Event Simulation. Springer Series in Statistics. Springer, New York (2004) · Zbl 1057.65002 · doi:10.1007/978-1-4757-4078-3
[15] Chan, J.C., Kroese, D.: Rare-event probability estimation with conditional Monte Carlo. Ann. Oper. Res. 189(1), 43-61 (2011) · Zbl 1279.60064 · doi:10.1007/s10479-009-0539-y
[16] Devroye, L.: Non-uniform Random Variate Generation. Springer, New York (1986) · Zbl 0593.65005 · doi:10.1007/978-1-4613-8643-8
[17] Dupuis, P., Leder, K., Wang, H.: Importance sampling for sums of random variables with regularly varying tails. ACM Trans. Model. Comput. Simul. 17(3), 14 (2007) · Zbl 1390.65002 · doi:10.1145/1243991.1243995
[18] Fenton, L.: The sum of Log-normal probability distributions in scatter transmission systems. IRE Trans. Commun. Syst. 8(1), 57-67 (1960) · doi:10.1109/TCOM.1960.1097606
[19] Filho, J.C.S.S., Yacoub, M.D.: Simple precise approximations to Weibull sums. IEEE Commun. Lett. 10(8), 614-616 (2006) · doi:10.1109/LCOMM.2006.1665128
[20] Ghavami, M., Kohno, R., Michael, L.: Ultra Wideband Signals and Systems in Communication Engineering. Wiley, Chichester (2004) · doi:10.1002/0470867531
[21] Hartinger, J., Kortschak, D.: On the efficiency of the Asmussen-Kroese-estimator and its application to stop-loss transforms. Blätter der DGVFM 30(2), 363-377 (2009) · Zbl 1182.91092 · doi:10.1007/s11857-009-0088-0
[22] Healey, A., Bianchi, C.H., Sivaprasad, K.: Wideband outdoor channel sounding at 2.4 GHz. In: Proceedings of the IEEE Conference on Antennas and Propagation for Wireless Communications, Waltham (2000)
[23] Hu, J., Beaulieu, N.C.: Accurate simple closed-form approximations to Rayleigh sum distributions and densities. IEEE Commun. Lett. 9(2), 109-111 (2005) · doi:10.1109/LCOMM.2005.02003
[24] Jelenkovic, P., Momcilovic, P.: Resource sharing with subexponential distributions. In: Proceedings of the IEEE 21st Annual Joint Conference of the Computer and Communications (INFOCOM’ 2002), New York (2002) · Zbl 1082.60083
[25] Juneja, S.: Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error. Queueing Syst. 57(2-3), 115-127 (2007) · Zbl 1145.90355 · doi:10.1007/s11134-007-9051-8
[26] Juneja, S., Shahabuddin, P.: Simulating heavy tailed processes using delayed hazard rate twisting. ACM Trans. Model. Comput. Simul. 12(2), 94-118 (2002) · Zbl 1390.65033 · doi:10.1145/566392.566394
[27] Kroese, D.P., Rubinstein, R.Y.: The transform likelihood ratio method for rare event simulation with heavy tails. Queueing Syst. 46(3), 317-351 (2004) · Zbl 1061.90032 · doi:10.1023/B:QUES.0000027989.97672.be
[28] Kroese, D.P., Taimre, T., Botev, Z.I.: Handbook of Monte Carlo Methods. Wiley, New York (2011) · Zbl 1213.65001 · doi:10.1002/9781118014967
[29] Nandayapa, L.R.: Risk Probabilities: Asymptotics and Simulation, P.hd. thesis, university of aarhus (2008) · Zbl 1097.65017
[30] Navidpour, S.M., Uysal, M., Kavehrad, M.: BER performance of free-space optical transmission with spatial diversity. IEEE Trans. Wirel. Commun. 6(8), 2813-2819 (2007) · doi:10.1109/TWC.2007.06109
[31] Rubinstein, R.Y., Kroese, D.P.: The Cross Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-carlo Simulation (Information Science and Statistics). Springer, Secaucus (2004) · Zbl 1140.90005
[32] Sadowsky, J.S.: On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans. Inf. Theory 39(1), 119-128 (1993) · Zbl 0766.62018 · doi:10.1109/18.179349
[33] Sadowsky, J.S., Bucklew, J.A.: On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theory 36(3), 579-588 (1990) · Zbl 0702.60029 · doi:10.1109/18.54903
[34] Sagias, N.C., Karagiannidis, G.K.: Gaussian class multivariate Weibull distributions: theory and applications in fading channels. IEEE Trans. Inf. Theory 51(10), 3608-3619 (2005) · Zbl 1283.94008 · doi:10.1109/TIT.2005.855598
[35] Schwartz, S.C., Yeh, Y.S.: On the distribution function and moments of power sums with Lognormal component. Bell Syst. Tech. J. 61, 1441-1462 (1982) · Zbl 0495.60028 · doi:10.1002/j.1538-7305.1982.tb04353.x
[36] Simon, M.K., Alouini, M.-S.: Digital Communication over Fading Channels, 2nd edn. Wiley, New York (2004) · doi:10.1002/0471715220
[37] Stüber, G.L.: Principles of Mobile Communication, 2nd edn. Kluwer Academic Publishers, Norwell (2001) · Zbl 0988.03016
[38] Yilmaz, F., Alouini, M.-S.: Sum of Weibull variates and performance of diversity systems. In: Proceedings of the International Wireless Communications and Mobile Computing Conference (IWCMC’2009), Leipzig (2009)
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.