<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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.</p></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.

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

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

We demonstrate an approach for exact sampling of certain discrete combinatorial distributions, which is a hybrid of exact Boltzmann sampling and the recursive...

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

Publié en ligne: 14 juil. 2017

Pages: 22 - 45

Reçu: 30 sept. 2016

DOI: https://doi.org/10.1515/puma-2015-0020

Mots clés
exact sampling, perfect simulation, probabilistic divide-and-conquer, Boltzmann sampler, random combinatorial structure, rejection sampling, recursive method

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

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

Publié en ligne: 14 juil. 2017

Pages: 22 - 45

Reçu: 30 sept. 2016

DOI: https://doi.org/10.1515/puma-2015-0020

Mots clésexact sampling, perfect simulation, probabilistic divide-and-conquer, Boltzmann sampler, random combinatorial structure, rejection sampling, recursive method

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
exact sampling, perfect simulation, probabilistic divide-and-conquer, Boltzmann sampler, random combinatorial structure, rejection sampling, recursive method