×

The cross-entropy method with patching for rare-event simulation of large Markov chains. (English) Zbl 1208.65020

Summary: There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a general state-dependent importance sampling method which partitions the state space and applies the cross-entropy method to each partition. We investigate two versions of our algorithm and apply them to several examples of reliability and queueing models. In all these examples we compare our method with other importance sampling schemes. The performance of the importance sampling schemes is measured by the relative error of the estimator and by the efficiency of the algorithm. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
62N05 Reliability and life testing
60J22 Computational methods in Markov chains
65C60 Computational problems in statistics (MSC2010)
62D05 Sampling theory, sample surveys

Software:

MARCA
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahamed, I.; Borkar, V. S.; Juneja, S., Adaptive importance sampling for Markov chains using stochastic approximation, Operations Research, 54, 489-504 (2006) · Zbl 1167.60343
[2] Alexopoulos, C.; Shultes, B. C., Estimating reliability measures for highly-dependable Markov systems using balanced likelihood ratios, IEEE Transactions on Reliability, 50, 265-280 (2001)
[3] Andradóttir, S.; Heyman, D. P.; Ott, T. J., On the choice of alternative measures in importance sampling with Markov chains, Operations Research, 43, 509-519 (1995) · Zbl 0842.60072
[4] Asmussen, S.; Rubinstein, R. Y., Steady-state rare-events simulation in queueing models and its complexity properties, (Dshalalow, J., Advances in Queueing: Models, Methods and Problems (1995), CRC Press: CRC Press Boca Raton), 429-466 · Zbl 0848.60085
[5] Boer, P. T.; Nicola, V. F., Adaptive state-dependent importance sampling simulation of Markovian queueing networks, European Transactions on Telecommunications, 13, 303-315 (2002)
[6] Bucklew, J. A., Introduction to Rare Event Simulation (2004), Springer · Zbl 1057.65002
[7] Bucklew, J. A.; Ney, P.; Sadowsky, J. S., Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains, Journal of Applied Probability, 27, 44-59 (1990) · Zbl 0702.60028
[8] Cover, T. M.; Thomas, J. A., Elements of Information Theory (2006), Wiley · Zbl 1140.94001
[9] Dayar, T.; Stewart, W. J., Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing, 21, 1691-1705 (2000) · Zbl 0957.60076
[10] de Boer, P. T., Analysis of state-independent importance sampling measures for the two-node tandem queue, ACM Transactions on Modeling and Computer Simulation, 16, 225-250 (2006) · Zbl 1390.90270
[11] de Boer, P. T.; Kroese, D. P.; Rubinstein, R. Y., Estimating buffer overflows in queueing networks, Management Science, 50, 7, 883-895 (2004) · Zbl 1232.90142
[12] Desai, P.; Glynn, P. W., A Markov chain perspective on adaptive Monte Carlo algorithms, (Peters, B.; Smith, J.; Medeiros, D.; Rohrer, M., Proceedings of 2001 Winter Simulation Conference (2001), IEEE Press), 379-384
[13] Devetsikiotis, M.; Towsend, J. K., An algorithmic approach to the optimization of importance sampling parameters in digital communication system simulation, IEEE Transactions on Communications, 41, 1464-1473 (1993) · Zbl 0800.94051
[14] Dupuis, P.; Wang, H., Dynamic importance sampling for uniformly recurrent Markov chains, Annals of Applied Probability, 15, 1-38 (2005) · Zbl 1068.60036
[15] Dupuis, P.; Sezer, D.; Wang, H., Dynamic importance sampling for queueing networks, Annals of Applied Probability, 17, 1306-1346 (2007) · Zbl 1144.60022
[16] Frater, M.; Lennon, T.; Anderson, B., Optimally efficient estimation of the statistics of rare events in queueing networks, IEEE Transactions on Automatic Control, 36, 1395-1405 (1991) · Zbl 0739.60080
[17] Garvels, M.J.J., 2000. The splitting method in rare event simulation. Ph.D. Thesis, Faculty of Mathematical Science, University of Twente, The Netherlands.; Garvels, M.J.J., 2000. The splitting method in rare event simulation. Ph.D. Thesis, Faculty of Mathematical Science, University of Twente, The Netherlands. · Zbl 1233.90114
[18] Glasserman, P.; Kou, S.-G., Analysis of an importance sampling estimator for tandem queues, ACM Transactions on Modeling and Computer Simulation, 5, 22-42 (1995) · Zbl 0841.62083
[19] Glasserman, P.; Heidelberger, P.; Shahabuddin, P.; Zajic, T., Multilevel splitting for estimating rare event probabilities, Operations Research, 47, 585-600 (1999) · Zbl 0985.65006
[20] Glynn, P. W.; Iglehart, D. L., Importance sampling for stochastic simulations, Management Science, 35, 1337-1392 (1989) · Zbl 0691.65107
[21] Goyal, A.; Shahabuddin, P.; Heidelberger, P.; Nicola, V. F.; Glynn, P. W., A unified framework for simulating Markovian models of highly dependable systems, IEEE Transactions on Computers, 41, 36-51 (1992)
[22] Heidelberger, P., Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modelling and Computer Simulation, 5, 43-85 (1995) · Zbl 0843.62096
[23] Ignatiouk-Robert, I., Large deviations for processes with discontinuous statistics, Annals of Probability, 33, 1292-1329 (2005) · Zbl 1025.60011
[24] Juneja, S.; Nicola, V. F., Efficient simulation of buffer overflow probabilities in Jackson networks with feedback, ACM Transactions on Modeling and Computer Simulation, 15, 281-315 (2005) · Zbl 1390.90224
[25] Juneja, S.; Shahabuddin, P., Fast simulation of Markov chains with small transition probabilities, Management Science, 47, 547-562 (2001) · Zbl 1232.90166
[26] Juneja, S.; Shahabuddin, P., Splitting based importance sampling algorithm for fast simulation of Markov reliability models with general repair policies, IEEE Transactions on Reliability, 50, 235-245 (2001)
[27] Juneja, S.; Shahabuddin, P., Rare-event simulation techniques: An introduction and recent advances, (Henderson, S.; Nelson, B., Handbooks in Operations Research and Management Science. Handbooks in Operations Research and Management Science, Simulation, vol. 13 (2006), Elsevier: Elsevier Amsterdam), 291-350
[28] Kollman, C.; Baggerly, K.; Cox, D.; Picard, R., Adaptive importance sampling on discrete Markov chains, Annals of Applied Probability, 9, 391-412 (1999) · Zbl 0939.65009
[29] Kroese, D. P.; Nicola, V. F., Efficient simulation of a tandem Jackson network, ACM Transactions on Modeling and Computer Simulation, 12, 119-141 (2002) · Zbl 1390.90231
[30] L’Ecuyer, P., Tuffin, B., 2007. Effective approximation of zero-variance simulation in a reliability setting. In: Sklenar, J., Bertelle, C., Fortino, G. (Eds.), Proceedings of the 2007 European Simulation and Modeling Conference, pp. 48-54.; L’Ecuyer, P., Tuffin, B., 2007. Effective approximation of zero-variance simulation in a reliability setting. In: Sklenar, J., Bertelle, C., Fortino, G. (Eds.), Proceedings of the 2007 European Simulation and Modeling Conference, pp. 48-54.
[31] L’Ecuyer, P.; Blanchet, J. H.; Tuffin, B.; Glynn, P. W., Asymptotic robustness of estimators in rare-event simulation, ACM Transactions on Modeling and Computer Simulation, 20 (2010), 6:1-6:41 · Zbl 1386.65066
[32] Nicola, V. F.; Zaburnenko, T. S., Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks, ACM Transactions on Modeling and Computer Simulation, 17, 2 (2006) · Zbl 1390.90249
[33] Parekh, S.; Walrand, J., A quick simulation method for excessive backlogs in networks of queues, IEEE Transactions on Automatic Control, 34, 54-66 (1989) · Zbl 0661.60110
[34] Randhawa, R.; Juneja, S., Combining importance sampling and temporal difference control variates to simulate Markov chains, ACM Transactions on Modelling and Computer Simulation, 14, 1-30 (2004) · Zbl 1390.65031
[35] (Rubino, G.; Tuffin, B., Rare Event Simulation Using Monte Carlo Methods (2009), Wiley) · Zbl 1159.65003
[36] Rubinstein, R. Y.; Kroese, D. P., The Cross-entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning (2004), Springer · Zbl 1061.90032
[37] Rubinstein, R. Y.; Kroese, D. P., Simulation and the Monte-Carlo Method (2007), Wiley · Zbl 1061.90032
[38] Shahabuddin, P., Importance sampling for simulation of highly reliable Markovian systems, Management Science, 40, 333-352 (1994) · Zbl 0805.90049
[39] Shahabuddin, P., Fast transient simulation of Markovian models of highly dependable systems, Performance Evaluation, 20, 267-286 (1994)
[40] Shwartz, A.; Weiss, A., Large Deviations for Performance Analysis (1995), Chapman & Hall
[41] Smith, P. J., Underestimation of Rare Event Probabilities in Importance Sampling Simulations, Simulation, 75, 140-150 (2001)
[42] Stewart, W. J., Numerical methods for computing stationary distributions of finite irreducible Markov chains, (Grassmann, W., Advances in Computational Probability (1999), Kluwer), (Chapter 3) · Zbl 0942.65010
[43] Stewart, W. J., Performance modeling and Markov chains, (Bernardo, M.; Hillston, J., Formal Methods for Performance Evaluation. SFM 2007. Formal Methods for Performance Evaluation. SFM 2007, LNCS, vol. 4486 (2007), Springer), 1-33 · Zbl 1323.68057
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.