Boltzmann sampling constitutes an efficient and simple method for the uniform random generation of combinatorial structures in decomposable classes, avoiding the costly precomputation of coefficients in the recursive method. However, since Boltzmann distribution is spread over the whole class, exact-size generators extracted from Boltzmann samplers typically have superlinear (e.g. quadratic) complexity, due to heavy rejection.
There are nevertheless cases where efficient exact-size implementations are possible: an example is the sequence construction (i.e., a class C=Seq(B)) in the supercritical case, where a known "leap" process on top of Boltzmann samplers yields an exact-size random generator with linear-time complexity.
As I will explain, the leap generation process extends to supercritical composition schemes C=AoB, yielding an exact-size sampler of linear time complexity (under conditions on the sampling complexity in A and B). While exact uniformity of the distribution is lost in general, asymptotic uniformity holds: the total variation distance to the uniform distribution is $\sim c/n^{1/2}$ for some explicit $c$, and can be made smaller using a simple rejection step.
A motivation for this work is that these leap generators can be applied to classes of unlabeled rooted trees such as Pólya trees. Experiments confirm the efficiency of the method and closeness to the uniform distribution.
Leap generators can also be developed for certain critical composition schemes, those relating families of planar maps, the total variation distance to the uniform distribution being this time $\sim c/n^{1/3}$ for some explicit $c$.
Joint work with Carine Pivoteau