<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

Published Online: Jul 14, 2017

Page range: 22 - 45

Received: Sep 30, 2016

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

Keywords
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

Published Online: Jul 14, 2017

Page range: 22 - 45

Received: Sep 30, 2016

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

Keywordsexact 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.

Keywords
exact sampling, perfect simulation, probabilistic divide-and-conquer, Boltzmann sampler, random combinatorial structure, rejection sampling, recursive method