稀有事件仿真算法综述

doi:10.16182/j.issn1004731x.joss.201809003

摘要/Abstract

摘要： 稀有事件因其发生概率很低、危害性较大而具有较高的研究价值,传统的蒙特卡洛方法很难对这一问题进行有效分析,稀有事件仿真技术可以通过方差缩减方法实现稀有事件的快速采样,进而对稀有事件发生的概率进行高效估计。近年来,该技术得到了快速的发展并广泛应用于多个领域,基于此,对稀有事件仿真算法的研究现状进行综述;概括、分析了主流算法的基本原理、存在的问题及研究进展;同时阐述和总结了算法的应用领域;探讨了稀有事件仿真技术未来的发展趋势。

关键词: 稀有事件, 重要性抽样, MCMC, 多分裂算法

Abstract: Rare-event has a great significance for its lower probability of occurrence and greater harmfulness, the traditional Monte Carlo method is difficult to analyze it effectively. Rare-event simulation technique which is developed quickly and applied in many areas can sample the rare-event effectively with variance reduction methods and can estimate the occurrence probability of rare-event. The research status of rare-event simulation technique is summarized firstly; the principles, problems and progress of the main methods are analyzed and concluded secondly; after that the application fields of the technique are elaborated and summarized; the future development tendency of rare event simulation technique is discussed finally.

Key words: rare event simulation, importance, MCMC, multi-level splitting

中图分类号:

TP391.9

王丽萍, 范文慧. 稀有事件仿真算法综述[J]. 系统仿真学报, 2018, 30(9): 3249-3254.

Wang Liping, Fan Wenhui. A Review of Rare Event Simulation[J]. Journal of System Simulation, 2018, 30(9): 3249-3254.

参考文献

[1] S Asmussen, P W Glynn.Stochastic Simulation: Algorithms and Analysis[M]. Springer, New York, 2007.
[2] Christian P Robert, George Casella.Monte Carlo Statistical Methods[M]. Springer, New York, 2004.
[3] Zdravko I Botev, Dirk P Kroese.An Efficient Algorithm for Rare-event Probability Estimation, Combinatorial Optimization, and Counting[J]. Methodol Comput Appl Probab (S1387-5841), 2008, 10(4): 471-505.
[4] L’Ecuyer P, B Tuffin. Approximating zero- variance importance sampling in a reliability setting[J]. Annals of Operations Research (S0254-5330), 2011, 189(1): 277-297.
[5] Bruno Tuffin, Saggadi S, Pierre L’Ecuyer. An adaptive zero-variance importance sampling approximation for static network dependability evaluation[J]. Computers and Operations Research (S0305-0548), 2014, 45(45): 51-59.
[6] Grace A W, Kroese D P, Sandmann W.Automated state-dependent importance sampling for Markov jump processes via sampling from the zero-variance distri- bution[J]. Journal of Applied Probability (S0021-9002), 2014, 51(3): 741-755.
[7] Marnix J J Garvels. The splitting method in rare event simulation[D]. PhD thesis, University Twente, 2000.
[8] Gao Fuqing.Moderate deviations and large deviations for kernel density estimators[J]. Journal of Theoretical Pro- bability (S0894-9840), 2003, 16(2): 401-418.
[9] A W Marshall.The use of multi-stage sampling schemes in Monte Carlo computations[J]. Symposium on Monte Carlo Methods. New York: Wiley (S0162-1459), 1956: 123-140.
[10] S Asmussen, P W Glynn.Stochastic Simulation[M]. New York: Springer-Verlag, 2007.
[11] G Rubino, B Tuffin, Eds. Rare Event Simulation using Monte Carlo Methods[M]. John Wiley & Sons, 2009.
[12] Rubinstein R Y, Kroese D P.The Cross-Entropy Method[J]. Technomitrics (S0040-1706), 2008, 50(1): 92-92.
[13] Qiu Yue.An Importance Sampling Method Based on Variance Minimization with Applications to Credit Risk[J]. Proceedings of the 29th Chinese Control Conference (S1531-5878), 2010, 3(3): 3176-3179.
[14] Bucklew J A.Large Deviation Techniques in Decision, Simulation and Estimation[M]. New York, Wiley, 1990.
[15] Rubinstein R.Optimization of computer simulation models with rare events[J]. European Journal of Operational Research (S0377-2217), 1997, 99(1): 89-112.
[16] Zhang P.Nonparametric importance sampling[J]. Journal of the American Statistical Association (S0162-1459), 1996, 91: 1245-1253.
[17] Sadowsky J, J Bucklew. On large deviations theory and asymptotically efficient Monte Carlo estimation[J]. IEEE transactions on Information Theory (S0018-9448), 1990, 36(3): 579-588.
[18] Chan J C C, Dirk P Kroese. Improved cross-entropy method for estimation[J]. Statistics and Computing (S0960-3174). 2012, 22(5): 1031-1040.
[19] Tim J Brereton, Joshua C.C Chan, Dirk P Kroese. Fitting Mixture Importance Sampling Distributions via Improved Cross-Entropy[J]. Proceedings of the 2011 Winter Simulation Conference (S0891-7736), 2012, 2(4): 422-428.
[20] Metropolis N, Rosenbluth A W, Rosenbluth M N, et al.Equations of state calculations by fast computing machines[J]. J. Chem. Phys (S0021-9606), 1953, 21(6): 1087-1092.
[21] Botev Z I, L’Ecuyer P, Tuffin B. Markov chain importance sampling with applications to rare event probability estimation[J]. Stat Comput (S0960-3174), 2013, 23(2): 271-285.
[22] YUYA SUZUKI.Rare-event Simulation with Markov Chain Monte Carlo[D]. MA thesis, Royal Institute of Technology, Stockholm, Sweden, 2013.
[23] C Kollman, K Baggerly, D Cox, et al.Adaptive importance sampling on discrete Markov chains[J]. Annals of Applied Probability (S1050-5164), 1999, 9(2): 391-412.
[24] T P Imthias Ahamed, V S Borkar, S Juneja. Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation[J]. Operations Research (S1109-2858), 2006, 54(3): 489-504.
[25] H Kahn, T E Harris.Estimation of particle transmission by random sampling[J]. National Bureau of Standards Appl. Math. Series, 1951, 12: 27-30.
[26] Bayes A J.Statistical techniques for simulation mo- dels[J]. The Australian Computer Journal (S0004-8917), 1970, 2(4): 180-184.
[27] Villén-Altamirano M, Villén-Altamirano J.RESTART: A straightforward method for fast simulation of rare events[J]. Proceedings of the 26th Winter simulation conference (S0891-7736), 1995, 79(6): 282-289.
[28] Villen-Altamirano M, Villen-Altamirano J.Analysis of restart simulation: Theoretical basis and sensitivity study[J]. European Transactions on Telecommunications (S1124-318X), 2002, 13(4): 373-385.
[29] Glasserman P, Heidelberger P, Shahabuddin P, et al.Multilevel splitting for estimating rare event probabi- lities[J]. Operation Research (S0030-364X), 1996, 47(4): 585-600.
[30] Haraszti Z, Townsend J K.The theory of direct probability redistribution and its application to rare event simulation[J]. Proc. of the IEEE international confer- ence on communications (S0090-6778), 1999, 9(2): 1443-1450.
[31] F Schreiber, C Görg.Rare event simulation: a modified RESTART method using the LRE algorithm[J]. Pr-oceedings 14th ITC, Antibes, France, June 6-10, Elsevier, North Holland (S1388-3437), 1994, 1: 787-796.
[32] F Schreiber.Effective control of simulation runs by a new evaluation algorithm for correlated random sequ- ences[J]. AEÜ(S1434-8411), 1988, 42(6): 347-354.
[33] Garvels M J J, Ommeren J K C W, Kroese D P. On the importance function in splitting simulation[J]. European Transaction on Telecommunications (S1124-318X), 2002, 13(4): 363-371.
[34] Paul Dupuis, Ali Devin Sezer, Hui Wang.Dynamic importance sampling for queueing networks[J]. The Annals of Applied Probability (S1050-5164), 2007, 17(4): 1306-1346.
[35] Haraszti Z, Townsend J K.The theory of direct probability redistribution and its application to rare event simulation[J]. ACM Transactions on Modelling and Computer Simulation (S1558-1195), 1999, 9(2): 1443-1450.
[36] Izabella Lokshina, Evan Schiele.Buffer Overflow Si- mulation in Self-Similar Queuing Networks with Finite Buffer Capacity Accelerated Using RESTART/LRE[J]. Wireless Telecommunications Symposium (WTS)(S1006-7043), 2015, 5(3): 1-7.
[37] A Ridder.Importance sampling simulations of Monrovian reliability systems using cross-entropy[J]. Annals of Operations Research (S0254-5330), 2005, 143(6): 119-136.
[38] M de Konling, W Cai, B Sadigh, et al. Adaptive importance sampling Monte Carlo simulation of rare transition events[J]. Journal of Chemical Physics (S0021-9606), 2005, 122(7): 074103.
[39] F Cerou, P Del Moral, F Le Gland, et al.Genetic genealogical models in rare event analysis[J]. ALEA, Latin American Journal of Probability and Mathematical Statistics (S1980-0436), 2006, 1: 181-203.
[40] Zdravko I Botev, Pierre L’Ecuyer, Richard Simard, et al. Static Network Reliability Estimation under the Marshall-Olkin Copula[J]. ACM Transactions on Modeling and Computer Simulation (S1558-1195), 2016, 26(2): 14.
[41] Y Chen, P Diaconis, S Holmes, et al.Sequential Monte Carlo methods for statistical analysis of tables[J]. Journal of the American Statistical Association (S0162-1459), 2005, 100(469): 109-120.
[42] Graham Mauch Donovan.Rare Event Simulation for Lightwave Systems Using the Cross-Entropy Method[D]. PhD thesis, Northwestern University, Illinois, USA, 2008.
[43] W Sandmann.Discrete-time stochastic modeling and simulation of biochemical networks[J]. Computational Biology and Chmistry (S1476-9271), 2008, 32(4): 292-297.
[44] Hong Zhou, Yue Qiu, Yueqin Wu.An Early Warning System for Loan Risk Assessment Based on Rare Event Simulation[J]. AsiaSim, CCIS, 2007, 5: 85-94.