# 11-062/4 (2011-04-07)

Paul Dupuis, Brown University, Providence, USA; Bahar Kaynar, VU University Amsterdam; Ad Ridder, VU University Amsterdam; Reuven Rubinstein, Technion, Haifa, Israel; Radislav Vaisman, Technion, Haifa, Israel
Counting, Gibbs Sampler, Capture-Recapture, Splitting
JEL codes:
C15, C63

This discussion paper resulted in a publication in Stochastic Models (2012). Volume 28(3), pages 478-502.

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.