Boltzmann samplers are 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 \(\mathscr{C}={\text{Seq}}(\mathscr{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.
In this joint work with Carine Pivoteau, we extend the leap generation process to supercritical composition schemes \(\mathscr{C}=\mathscr{A}\circ\mathscr{B}\), yielding an exact-size sampler of linear time complexity (under conditions on the sampling complexity in \(\mathscr{A}\) and \(\mathscr{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\).
Localisation
Salle de séminaire 4B107 (bâtiment Copernic)
5, boulevard Descartes, 77420 Champs-sur-Marne