Operations Management and Econometrics Seminar

Efficient Estimation via Generalised Splitting

Professor Dirk Kroese, The University of Queensland

9th Apr 2010  11:00 am - Room 498 Merewether Building

Adaptive importance sampling techniques such as the cross-entropy method have proved to be very useful in rare-event probability estimation. However, for high-dimensional problems the importance sampling estimator can become unreliable, due to the degeneration of the likelihood ratio.  We propose a new rare-event estimation method based on the classical splitting idea of Kahn and Harris. The new method does not use importance sampling, is non-parametric, and remains stable in higher dimensions. We demonstrate its effectiveness by estimating the number of solutions in the satisfiability (SAT) problem.