An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting

DOI10.1007/s11009-008-9073-7zbMath1293.65004OpenAlexW2055755416WikidataQ56689537 ScholiaQ56689537MaRDI QIDQ398785

Dirk P. Kroese, Zdravko I. Botev

Publication date: 15 August 2014

Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11009-008-9073-7

zbMATH Keywords

importance samplingkernel density estimationexact samplingcombinatorial countinglikelihood ratio degeneracyrare-event probability estimation

Mathematics Subject Classification ID

Computational learning theory (68Q32) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Related Items (28)

Layered adaptive importance sampling ⋮ Counting with Combined Splitting and Capture–Recapture Methods ⋮ Some Recent Results in Rare Event Estimation ⋮ Combinatorial analysis of the adaptive last particle method ⋮ Splitting for multi-objective optimization ⋮ Stochastic enumeration method for counting NP-hard problems ⋮ Interacting particle system based estimation of reach probability of general stochastic hybrid systems ⋮ Stochastic approximation Monte Carlo importance sampling for approximating exact conditional probabilities ⋮ Tensor product approach to modelling epidemics on networks ⋮ Random assignment versus fixed assignment in multilevel importance splitting for estimating stochastic reach probabilities ⋮ Deep Importance Sampling Using Tensor Trains with Application to a Priori and a Posteriori Rare Events ⋮ Adaptive multilevel splitting: Historical perspective and recent results ⋮ Simulation and estimation of extreme quantiles and extreme probabilities ⋮ Rare-event probability estimation with conditional Monte Carlo ⋮ A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem ⋮ A combined splitting-cross entropy method for rare-event probability estimation of queueing networks ⋮ Uncertainty quantification of stochastic simulation for black-box computer experiments ⋮ Stochastic enumeration method for counting trees ⋮ Sequential Monte Carlo for rare event estimation ⋮ HOW TO GENERATE UNIFORM SAMPLES ON DISCRETE SETS USING THE SPLITTING METHOD ⋮ Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work ⋮ Rare event simulation and splitting for discontinuous random variables ⋮ A binary differential search algorithm for the 0-1 multidimensional knapsack problem ⋮ An adaptive metamodel-based subset importance sampling approach for the assessment of the functional failure probability of a thermal-hydraulic passive system ⋮ Efficient Monte Carlo simulation via the generalized splitting method ⋮ A control based on a knapsack problem for solar hydrogen production ⋮ The Gibbs cloner for combinatorial optimization, counting and sampling ⋮ On the Use of Smoothing to Improve the Performance of the Splitting Method

Uses Software

• RESTART

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rare event restart simulation of two-stage networks
• The cross-entropy method for continuous multi-extremal optimization
• Two-stage nested partitions method for stochastic optimization
• Introduction to rare event simulation.
• The cross-entropy method for combinatorial and continuous optimization
• How many needles are in a haystack, or how to solve \#P-complete counting problems fast
• A stochastic minimum cross-entropy method for combinatorial optimization and rare-event estimation
• Sequential Monte Carlo Methods in Practice
• Exact sampling with coupled Markov chains and applications to statistical mechanics

This page was built for publication: An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting