Amir Jalaly BIDGOLY, Mohammad Abdollahi AZGOMI

A new technique for rare-event simulation based on partition of the region

Rare events are an important limitation of discrete-event simulation in some areas of applications. The existing rare-event simulation (RES) techniques, such as importance sampling (IS), splitting, and RESTART, have been used for RES so far. However, these techniques not only have some limitations, but also are not general or easy to use. In this paper, the partition of the region (PoR) method is used as a variance reduction technique in a new RES technique for usage with a wide range of modeling and simulation languages. Three variants of the proposed technique will be introduced: simple PoR, recursive PoR, and advanced PoR. Simple and recursive PoR methods are powerful techniques that have some important features such as bounded relative error; however, they are restricted to some specific models. Advanced PoR is a more general technique that integrates the PoR method and the IS technique. To evaluate the efficiency of the proposed technique and its variants, the comparative simulation results of some illustrative examples using stochastic activity networks will be presented.

Anahtar Kelimeler:

Rare-event simulation, variance reduction technique, partition of the region, simple partition of the region, recursive partition of the region, advanced partition of the region

A new technique for rare-event simulation based on partition of the region

Keywords:

Rare-event simulation, variance reduction technique, partition of the region, simple partition of the region, recursive partition of the region, advanced partition of the region,

PDF

___

S. Juneja, P. Shahabuddin, “Rare-event simulation techniques: an introduction and recent advances”, in: Handbook of Simulation, Handbooks in Operations Research and Management Science, Amsterdam, Elsevier, Vol. 13, pp. 291– 350, 2006.
P. Shahabuddin, “Importance sampling for the simulation of highly reliable Markovian systems”, Journal of Management Science, Vol. 40, pp. 333–352, 1994.
P.W. Glynn, D.L. Iglehart, “Importance sampling for stochastic simulations”, Journal of Management Science, Vol. 35, pp. 1367–1392, 1989.
P. L’Ecuyer, V. Demers, B. Tuﬃn, “Splitting for rare-event simulation”, Proceedings of the 2006 Winter Simulation Conference, pp. 137–148, 2006.
H. Kahn, T.E. Harris, “Estimation of particle transmission by random sampling”, National Bureau of Standards Applied Mathematics Series, Vol. 12, pp. 27–30, 1951.
P. Heidelberger, P. Glasserman, P. Shahabuddin, T. Zajic, “Splitting for rare event simulation: analysis of simple cases”, Proceedings of the 1996 Simulation Conference, pp. 302–308, 1996.
P.T. de Boer, V.F. Nicola, R.Y. Rubinstein, “Adaptive importance sampling simulation of queueing networks”, Proceedings of 2000 the Winter Simulation Conference Vol. 1, pp. 646–655, 2000.
M. Vill`en-Altamirano, J. Vill`en-Altamirano, “RESTART: a method for accelerating rare event simulations”, Queueing Performance and Control in ATM, pp. 71–76, 1991.
M. Vill`en-Altamirano, J. Vill`en-Altamirano, “RESTART: a straightforward method for fast simulation of rare events”, Proceedings of the 1994 Winter Simulation Conference, pp. 282–289, 1994.
A.J. Bidgoly, M.A. Azgomi, “Rare event simulation of stochastic activity networks using partition of the region technique”, Proceedings of the 24th UK Performance Engineering Workshop, pp. 107–122, 2008.
A.J. Bidgoly, M.A. Azgomi, A. Khalili, “An advanced technique for rare-event simulation based on partition of the region”, Proceedings of the 10th International Middle Eastern Simulation Multiconference, pp. 5–10, 2009.
R.Y. Rubinstein, Simulation and Monte Carlo Method, New York, Wiley, 2009.
W.H. Sanders, J.F. Meyer, “Stochastic activity networks: formal deﬁnitions and concepts”, Lectures on Formal Methods and Performance Analysis, pp. 315–343, 2001.
G. Rubino, B. Tuﬃn, Rare Event Simulation Using Monte Carlo Methods, New York, Wiley, 2009.
D.R. Cox, D.V. Hinkley, Theoretical Statistics, London, Chapman & Hall, 1974.
V.F. Nicola, M.K. Nakayama, P. Heidelberger, A. Goyal, “Fast simulation of highly dependable systems with general failure and repair processes”, IEEE Transactions on Computers, Vol. 40, pp. 1440–1452, 1993.
W.D. Obal 2nd, “Importance sampling simulation of SAN-based reward models”, MSc, University of Arizona, USA, 19 C. Kollman, K. Baggerly, D. Cox, R. Picard, “Adaptive importance sampling on discrete Markov chains”, Annals of Applied Probability, pp. 391–412, 1999.
P. Heidelberger, “Fast simulation of rare events in queueing and reliability models”, ACM Transactions on Modeling and Computer Simulation, Vol. 5, p. 43–85, 1995.
P. L’Ecuyer, J.H. Blanchet, B. Tuﬃn, P.W. Glynn, “Asymptotic robustness of estimators in rare-event simulation”, ACM Transactions on Modeling and Computer Simulation, Vol. 20, pp. 6:1–6:41, 2010.
A. Movaghar, J.F. Meyer, “Performability modeling with stochastic activity networks”, Proceedings of the 1984 Real-Time Systems Symposium, pp. 215–224, 1984.
W.H. Sanders, W.D. Obal 2nd, M.A. Qureshia, F.K. Widjanarko, “The UltraSAN modeling environment”, Performance Evaluation, Vol. 24, pp. 89–115, 1995.
D.D. Deavours, G. Clark, T. Courtney, D. Daly, S. Derisavi, J.M. Doyle, W.H. Sanders, P.G. Webster, “The Mobius framework and its implementation”, IEEE Transactions on Software Engineering, Vol. 28, pp. 956–969, 2002. A. Khalili, A.J. Bidgoly, M.A. Azgomi, “PDETool: A multi-formalism modeling tool for discrete-event systems based on SDES description”, Proceedings of the 30th International Conference on Application and Theory of Petri Nets and Other Models of Concurrency, Vol. 5606, pp. 343–352, 2009.
S. Lazarova-Molnar, “The proxel-based method: formalisation, analysis and applications”, PhD, der Otto-vonGuericke-University, Germany, 2005.
C. Isensee, G. Horton, “Fast simulation without randomness: a simulation tool combining proxels and discrete phases”, Proceedings of the 18th Symposium Simulationstechnik, 2005.
P. Glasserman, Monte Carlo Methods in Financial Engineering, Berlin, Heidelberg, Springer-Verlag, 2004.
B. Tuﬃn, “Bounded normal approximation in simulations of highly reliable Markovian systems”, Journal of Applied Probability, Vol. 36, pp. 974–986, 1999.
B. Tuﬃn, “On numerical problems in simulations of highly reliable Markovian systems”, Proceedings of the 1st International Conference on the Quantitative Evaluation of Systems, pp. 156–164, 2004.
A. Zimmermann, “RESTART simulation of colored stochastic Petri nets”, Proceedings of the 7th International Workshop on Rare Event Simulation, pp. 143–152, 2008.
S.R. Agnihothri, “Interrelationships between performance measures for the machine-repairman problem”, Naval Research Logistics, Vol. 36, pp. 265–271, 1989.
SimGine homepage, URL: http://pdel.iust.ac.ir/projects/SimGine.html.