Counting with combined splitting and capture--recapture methods

DOI10.1080/15326349.2012.699761MaRDI QIDQ3167896zbMATH OpenOpenAlexFDO

Authors Paul Dupuis, A. Ridder, Radislav Vaisman, Bahar Kaynar, Reuven Y. Rubinstein

Publication date 29 October 2012

Published in Stochastic Models (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.6096

zbMATH Keywords

3-SATalgorithmbinary contingency tablescapture-recapturecountingGibbs samplernumerical examplesrandom graphssatisfiability problem (SAT)splitting

Mathematics Subject Classification ID

Combinatorial probability (60C05) Monte Carlo methods (65C05) Stochastic particle methods (65C35) Randomized algorithms (68W20)

Abstract: We apply the splitting method to three well-known counting problems, namely 3-SAT, random graphs with prescribed degrees, and binary contingency tables. We present an enhanced version of the splitting method based on the capture-recapture technique, and show by experiments the superiority of this technique for SAT problems in terms of variance of the associated estimators, and speed of the algorithms.

Recommendations

• The splitting method for decision making
• Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
• On the use of smoothing to improve the performance of the splitting method
• Stochastic enumeration method for counting trees
• How to count quickly and accurately: a unified analysis of probabilistic counting and other related problems

Cites work

• A combined splitting-cross entropy method for rare-event probability estimation of queueing networks
• A Two-Step Branching Splitting Model Under Cost Constraint for Rare Event Analysis
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• Efficient Monte Carlo simulation via the generalized splitting method
• Inference from iterative simulation using multiple sequences
• Multilevel splitting for estimating rare event probabilities
• Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
• Rare events, splitting, and quasi-Monte Carlo
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Simulation and the Monte Carlo Method
• The complexity of computing the permanent
• Theory and Applications of Satisfiability Testing

Cited in

(3)

• Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
• On the use of smoothing to improve the performance of the splitting method
• The splitting method for decision making

This page was built for publication: Counting with combined splitting and capture--recapture methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167896)