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: email@example.com Author-Workplace-Name: Brown University, Providence, USA Author-Name: Bahar Kaynar Author-Email: firstname.lastname@example.org Author-Workplace-Name: VU University Amsterdam Author-Name: Ad Ridder Author-Email: email@example.com Author-Workplace-Name: VU University Amsterdam Author-Name: Reuven Rubinstein Author-Email: firstname.lastname@example.org Author-Workplace-Name: Technion, Haifa, Israel Author-Name: Radislav Vaisman Author-Email: email@example.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 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. Classification-JEL: C15, C63 Keywords: Counting, Gibbs Sampler, Capture-Recapture, Splitting File-Url: http://papers.tinbergen.nl/11062.pdf File-Format: application/pdf File-Size: 210457 bytes Handle: RePEc:tin:wpaper:20110062