Find us on Facebook Find us on LinkedIn Follow us on Twitter Subscribe to our YouTube channel

Operations Management and Econometrics

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.