Boltzmann sampling of irreducible context-free structures in linear time

Abstract

We continue our program of improving the complexity of so-called Boltzmann sampling algorithms, for the exact sampling of combinatorial structures, and reach average linear-time complexity, i.e. optimality up to a multiplicative constant. Here we solve this problem for irreducible context-free structures, a broad family of structures to which the celebrated Drmota--Lalley--Woods Theorem applies. Our algorithm is a rejection algorithm. The main idea is to single out some degrees of freedom, i.e. write $p(x)=p_1(y)p_2(x|y)$, which allows to introduce a rejection factor at the level of the $y$ object, that is almost surely of order $1$.

29 pages

References in corpus (4)

• Algorithms for Combinatorial Systems: Well-Founded Systems and Newton Iterations
• Multi-dimensional Boltzmann Sampling of Languages
• A new bijection on m-Dyck paths with application to random sampling
• Random generation of combinatorial structures: Boltzmann samplers and beyond

Cited by in corpus (1)

• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions