<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

Publicado en línea: 14 jul 2017

Páginas: 22 - 45

Recibido: 30 sept 2016

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

Palabras clave
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

Publicado en línea: 14 jul 2017

Páginas: 22 - 45

Recibido: 30 sept 2016

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

Palabras claveexact 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.

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