Convergence properties of the cross-entropy method for discrete optimization

We present new theoretical convergence results on the cross-entropy (CE) method for discrete optimization. We show that a popular implementation of the method converges, and finds an optimal solution with probability arbitrarily close to 1. We also give conditions under which an optimal solution is generated eventually with probability 1.