Boltzmann samplers for first-order differential specifications

In the framework of analytic combinatorics, Boltzmann models give rise to efficient algorithms for the random generation of combinatorial objects. This paper proposes an efficient Boltzmann sampler for ordered structures defined by first-order differential specifications. Under an abstract real-arithmetic computation model, our algorithm is of linear complexity for free generation; in addition, for many classical structures, the complexity is also linear when a small tolerance is allowed on the size of the generated object. The resulting implementation makes it possible to generate very large random objects, such as increasing trees, in a few seconds on a standard machine.