Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method

2016/08/29 by Stephen DeSalvo, DeSalvo, Stephen
Mathematics · Physics and Astronomy · #60C05 #65C50 #90-04 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Mechanics and Entropy #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1608.07922

openalex publication_date 2016/08/29 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We demonstrate an approach for exact sampling of certain discrete combinatorial distributions, which is a hybrid of exact Boltzmann sampling and the recursive method, using probabilistic divide-and-conquer (PDC). The approach specializes to exact Boltzmann sampling in the trivial setting, and specializes to PDC deterministic second half in the first non-trivial application. A large class of examples is given for which this method broadly applies, and several examples are worked out explicitly.

Related

• Random generation of combinatorial structures: Boltzmann samplers and beyond
• Probabilistic divide-and-conquer: deterministic second half
• Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example
• Exact sampling algorithms for Latin squares and Sudoku matrices via\n probabilistic divide-and-conquer
• Analytic Samplers and the Combinatorial Rejection Method