Template-Type: ReDIF-Paper 1.0
Series: Tinbergen Institute Discussion Papers
Creation-Date: 2011-04-07
Number: 11-062/4
Author-Name: Paul Dupuis
Author-Email: dupuis@dam.brown.edu
Author-Workplace-Name: Brown University, Providence, USA
Author-Name: Bahar Kaynar
Author-Email: b.kaynar@vu.nl
Author-Workplace-Name: VU University Amsterdam
Author-Name: Ad Ridder
Author-Email: ad.ridder@vu.nl
Author-Workplace-Name: VU University Amsterdam
Author-Name: Reuven Rubinstein
Author-Email: ierrr01@ie.technion.ac.il
Author-Workplace-Name: Technion, Haifa, Israel
Author-Name: Radislav Vaisman
Author-Email: slvaisman@gmail.com
Author-Workplace-Name: Technion, Haifa, Israel
Title: Counting with Combined Splitting and Capture-Recapture Methods
Abstract: This discussion paper resulted in a publication in <A HREF="https://www.tandfonline.com/doi/abs/10.1080/15326349.2012.699761"><I>Stochastic Models</I></A> (2012). Volume 28(3), pages 478-502.<P>

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.
Classification-JEL: C15, C63
Keywords: Counting, Gibbs Sampler, Capture-Recapture, Splitting
File-Url: https://papers.tinbergen.nl/11062.pdf
File-Format: application/pdf
File-Size: 210457 bytes
Handle: RePEc:tin:wpaper:20110062