Analytic Samplers and the Combinatorial Rejection Method

Boltzmann samplers introduced by Duchon et al. in 2001 is a method by which to automatically build random samplers from a combinatorial class ’ symbolic specification. But after over a decade, no complete standalone implementation of these samplers has been achieved. This paper describes how to address the primary roadbloack: that the concept at the heart of Boltzmann sampling, evaluating generating functions which are sometimes only known implicitly, is difficult to implement automatically and efficiently enough. By adapting the rejection method, a classical tool from the random sampling literature, we show how to bypass this issue almost entirely. We then redefine the Boltzmann sampler framework and show how to build concretely useful and efficient algorithms. Our work radically simplifies much of the computational burden that was previously associated with Boltzmann samplers, and hints at future powerful extensions.