Counting with Combined Splitting and Capture-Recapture Methods

Paul Dupuis (), Bahar Kaynar (), Ad Ridder (), Reuven Rubinstein () and Radislav Vaisman ()
Additional contact information
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

No 11-062/4, Tinbergen Institute Discussion Papers from Tinbergen Institute

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.

Keywords: Counting; Gibbs Sampler; Capture-Recapture; Splitting (search for similar items in EconPapers)
JEL-codes: C15 C63 (search for similar items in EconPapers)
Date: 2011-04-07
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://papers.tinbergen.nl/11062.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tin:wpaper:20110062

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute Contact information at EDIRC.
Bibliographic data for series maintained by Tinbergen Office +31 (0)10-4088900 ().