Minimizing sample size of Monte Carlo simulations by means of Cross-Entropy method

Tran Van Ly * , Ly Ngoc Thanh , Le Phat Tai , Le Thi Thuy An , Vo Thi Cam Tien and Bui Thi Thuy Trang

* Corresponding author (tvly@ctu.edu.vn)

Article Sidebar

Full Text: PDF

Received: 03 Oct 2022
Revised: 29 Oct 2022
Accepted: 03 Nov 2022
Published: 28 Apr 2023
Title: Minimizing sample size of Monte Carlo simulations by means of Cross-Entropy method
DOI: 10.22144/ctu.jvn.2023.063
Views
133
Downloads
117
Crossref
Scopus
Google Scholar
Europe PMC
How to Cite
Lý, T. V., Thanh, L. N., Tài, L. P., An, L. T. T., Tiên, V. T. C., & Trang, B. T. T. (2023). Minimizing sample size of Monte Carlo simulations by means of Cross-Entropy method. CTU Journal of Science, 59(2), 47-53. https://doi.org/10.22144/ctu.jvn.2023.063
Issue
Vol. 59 No. 2 (2023)
Section
Natural Sciences

Abstract

The limitation of the method Monte Carlo Naïve (MCN) was presented in this paper. This method is used to estimate the probability of rare events (events with very small probability). In the MCN method, to be able to observe rare events, it is necessary to initialize very large simulation samples. This limitation can be solved by using the Cross Entropy (CE) algorithm. The numerical results presented in the last section will further clarify the superiority of this method.

Keywords: Change of probability measure, cross Entropy, Monte Carlo method, rare event

Tóm tắt

Bài viết trình bày một số hạn chế của phương pháp mô phỏng Monte Carlo cơ bản (Monte Carlo Naïve - MCN). Phương pháp này được sử dụng để ước lượng xác suất sự kiện hiếm (các sự kiện có xác suất xảy ra rất bé). Trong phương pháp MCN, để có thể quan sát được những sự kiện hiếm cần phải khởi tạo các mẫu mô phỏng có kích thước rất lớn. Hạn chế này có thể được giải quyết bằng cách sử dụng một thuật toán Entropy chéo (Cross Entropy - CE). Kết quả áp dụng số được trình bày ở phần cuối cùng sẽ làm rõ hơn tính ưu việt của phương pháp này.

Từ khóa: Entropy chéo, đổi độ đo xác suất, phương pháp Monte Carlo, sự kiện hiếm

Article Details

References

Brémaud, P. (1999). Markov chains – Gibbs Fields, Monter Carlo Simulation and Queues. Spinger – New York. https://doi.org/10.1007/978-1-4757-3124-8

De Boer, P.T., Kroese, D.P., Mannor, S. & Rubinstein, R. Y. (2005). A Tutorial on the Cross- Entropy Method. Annals of Operations Research, 134,19-67.

https://doi.org/10.1007/s10479-005-5724-z

Homem-de-Mello T. & Rubinstein, R. Y. (2002). Estimation of rare event probabilities using cross-entropy. Proceedings of the Winter Simulation Conference, vol.1, 310-319. https://doi.org/10.1109/WSC.2002.1172900

Levine, R. A., & Casella, G. (2006). Optimizing random scan gibbs samplers. Journal of Multivariate Analysis, 97, 2071-2100. https://doi.org/10.1016/j.jmva.2006.05.008

Rubinstein, R. Y., & Kroese, D. P. (2017). Simulation and the Monte Carlo method (Wiley Series in Probability and Statistics). John Wiley & Sons, Inc., Hoboken, NJ.

https://doi.org/10.1002/9781118631980

Zhao, D., Lam, H., Peng, H., Bao, S., LeBlanc, D. J., Nobukawa, K., & Pan, C. S. (2017). Accelerated Evaluation of Automated Vehicles Safety in Lane-Change Scenarios Based on Importance Sampling Techniques. IEEE Transactions on Intelligent Transportation Systems, 18(3), 595-607. https://doi.org/10.1109/TITS.2016.2582208