IDEAS home Printed from https://ideas.repec.org/p/tin/wpaper/20110062.html
   My bibliography  Save this paper

Counting with Combined Splitting and Capture-Recapture Methods

Author

Listed:
  • 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)

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.

Suggested Citation

  • Paul Dupuis & Bahar Kaynar & Ad Ridder & Reuven Rubinstein & Radislav Vaisman, 2011. "Counting with Combined Splitting and Capture-Recapture Methods," Tinbergen Institute Discussion Papers 11-062/4, Tinbergen Institute.
    • Handle: RePEc:tin:wpaper:20110062
    as

    Download full text from publisher

    File URL: https://papers.tinbergen.nl/11062.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Reuven Rubinstein, 2010. "Randomized Algorithms with Splitting: Why the Classic Randomized Algorithms Do Not Work and How to Make them Work," Methodology and Computing in Applied Probability, Springer, vol. 12(1), pages 1-50, March.
    2. Zdravko I. Botev & Dirk P. Kroese, 2008. "An Efficient Algorithm for Rare-event Probability Estimation, Combinatorial Optimization, and Counting," Methodology and Computing in Applied Probability, Springer, vol. 10(4), pages 471-505, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kleijnen, Jack P.C. & Ridder, A.A.N. & Rubinstein, R.Y., 2010. "Variance Reduction Techniques in Monte Carlo Methods," Other publications TiSEM 87680d1a-53c1-4107-ada4-7, Tilburg University, School of Economics and Management.
    2. Hao Ma & Henk A. P. Blom, 2022. "Random Assignment Versus Fixed Assignment in Multilevel Importance Splitting for Estimating Stochastic Reach Probabilities," Methodology and Computing in Applied Probability, Springer, vol. 24(4), pages 2313-2338, December.
    3. Reuven Rubinstein, 2009. "The Gibbs Cloner for Combinatorial Optimization, Counting and Sampling," Methodology and Computing in Applied Probability, Springer, vol. 11(4), pages 491-549, December.
    4. Ali Eshragh & Jerzy Filar & Michael Haythorpe, 2011. "A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem," Annals of Operations Research, Springer, vol. 189(1), pages 103-125, September.
    5. Turati, Pietro & Pedroni, Nicola & Zio, Enrico, 2016. "Advanced RESTART method for the estimation of the probability of failure of highly reliable hybrid dynamic systems," Reliability Engineering and System Safety, Elsevier, vol. 154(C), pages 117-126.
    6. Sonal, S.D. & Ammanagi, S & Kanjilal, O & Manohar, C.S., 2018. "Experimental estimation of time variant system reliability of vibrating structures based on subset simulation with Markov chain splitting," Reliability Engineering and System Safety, Elsevier, vol. 178(C), pages 55-68.
    7. Youngjun Choe & Henry Lam & Eunshin Byon, 2018. "Uncertainty Quantification of Stochastic Simulation for Black-box Computer Experiments," Methodology and Computing in Applied Probability, Springer, vol. 20(4), pages 1155-1172, December.
    8. Joshua Chan & Dirk Kroese, 2011. "Rare-event probability estimation with conditional Monte Carlo," Annals of Operations Research, Springer, vol. 189(1), pages 43-61, September.
    9. Qibin Duan & Dirk P. Kroese, 2018. "Splitting for Multi-objective Optimization," Methodology and Computing in Applied Probability, Springer, vol. 20(2), pages 517-533, June.
    10. Radislav Vaisman & Dirk P. Kroese, 2017. "Stochastic Enumeration Method for Counting Trees," Methodology and Computing in Applied Probability, Springer, vol. 19(1), pages 31-73, March.
    11. Reuven Rubinstein, 2013. "Stochastic Enumeration Method for Counting NP-Hard Problems," Methodology and Computing in Applied Probability, Springer, vol. 15(2), pages 249-291, June.
    12. Francesco Di Maio & Nicola Pedroni & Barnabás Tóth & Luciano Burgazzi & Enrico Zio, 2021. "Reliability Assessment of Passive Safety Systems for Nuclear Energy Applications: State-of-the-Art and Open Issues," Energies, MDPI, vol. 14(15), pages 1-17, August.
    13. M. Garvels, 2011. "A combined splitting—cross entropy method for rare-event probability estimation of queueing networks," Annals of Operations Research, Springer, vol. 189(1), pages 167-185, September.
    14. Reuven Rubinstein, 2010. "Randomized Algorithms with Splitting: Why the Classic Randomized Algorithms Do Not Work and How to Make them Work," Methodology and Computing in Applied Probability, Springer, vol. 12(1), pages 1-50, March.
    15. Chan, Jianpeng & Papaioannou, Iason & Straub, Daniel, 2022. "An adaptive subset simulation algorithm for system reliability analysis with discontinuous limit states," Reliability Engineering and System Safety, Elsevier, vol. 225(C).

    More about this item

    Keywords

    Counting; Gibbs Sampler; Capture-Recapture; Splitting;
    All these keywords.

    JEL classification:

    • C15 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods and Methodology: General - - - Statistical Simulation Methods: General
    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:tin:wpaper:20110062. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tinbergen Office +31 (0)10-4088900 (email available below). General contact details of provider: https://edirc.repec.org/data/tinbenl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.