An Efficient Algorithm for Rare-event Probability Estimation, Combinatorial Optimization, and Counting

Zdravko I. Botev () and Dirk P. Kroese
Additional contact information
Zdravko I. Botev: University of Queensland
Dirk P. Kroese: University of Queensland

Methodology and Computing in Applied Probability, 2008, vol. 10, issue 4, 471-505

Abstract: Abstract Although importance sampling is an established and effective sampling and estimation technique, it becomes unstable and unreliable for high-dimensional problems. The main reason is that the likelihood ratio in the importance sampling estimator degenerates when the dimension of the problem becomes large. Various remedies to this problem have been suggested, including heuristics such as resampling. Even so, the consensus is that for large-dimensional problems, likelihood ratios (and hence importance sampling) should be avoided. In this paper we introduce a new adaptive simulation approach that does away with likelihood ratios, while retaining the multi-level approach of the cross-entropy method. Like the latter, the method can be used for rare-event probability estimation, optimization, and counting. Moreover, the method allows one to sample exactly from the target distribution rather than asymptotically as in Markov chain Monte Carlo. Numerical examples demonstrate the effectiveness of the method for a variety of applications.

Keywords: Likelihood ratio degeneracy; Kernel density estimation; Importance sampling; Exact sampling; Rare-event probability estimation; Combinatorial counting; 65C05; 65C60; 65C40; 68Q32 (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-008-9073-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:10:y:2008:i:4:d:10.1007_s11009-008-9073-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-008-9073-7

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().