The cross entropy method


A trick in Monte Carlo simulation, particularly rejection sampling, to optimise an proposal distribution. This notebook exists because I need to quickly audition this method for solving a problem and the wikipedia explanation is incomprehensible. I will create an explanatory example here and put it in Wikipedia. Maybe.

Boer, Pieter-Tjerk de, Dirk P. Kroese, Shie Mannor, and Reuven Y. Rubinstein. 2005. “A Tutorial on the Cross-Entropy Method.” Annals of Operations Research 134 (1): 19–67. https://doi.org/10.1007/s10479-005-5724-z.

Botev, Zdravko I., Dirk P. Kroese, Reuven Y. Rubinstein, and Pierre L’Ecuyer. 2013. “Chapter 3 - the Cross-Entropy Method for Optimization.” In Handbook of Statistics, edited by C. R. Rao and Venu Govindaraju, 31:35–59. Handbook of Statistics. Elsevier. https://doi.org/10.1016/B978-0-444-53859-8.00003-5.

Rubinstein, Reuven Y. 1997. “Optimization of Computer Simulation Models with Rare Events.” European Journal of Operational Research 99 (1): 89–112. https://doi.org/10.1016/S0377-2217(96)00385-2.

Rubinstein, Reuven Y, and Dirk P Kroese. 2004. The Cross-Entropy Method a Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. New York, NY: Springer New York. http://dx.doi.org/10.1007/978-1-4757-4321-0.

Rubinstein, Reuven Y., and Dirk P. Kroese. 2016. Simulation and the Monte Carlo Method. 3 edition. Wiley Series in Probability and Statistics. Hoboken, New Jersey: Wiley.