TY - GEN

T1 - Dirichlet random samplers for multiplicative structures

AU - Bodini, Olivier

AU - Lumbroso, Jérémie

PY - 2012/1/1

Y1 - 2012/1/1

N2 - In 2001, Duchon, Flajolet, Louchard and Schaeffer introduced Boltzmann samplers, a radically novel way to efficiently generate huge random combinatorial objects without any preprocessing; the insight was that the probabilities can be obtained directly by evaluating the generating functions of combinatorials classes. Over the following decade, a vast array of papers has increased the formal expressiveness of these random samplers. Our paper introduces a new kind of sampler which generates multiplicative combinatorial structures, which enumerated by Dirichlet generating functions. Such classes, which are significantly harder to analyze than their additive counterparts, are at the intersection of combinatorics and analytic number theory. Indeed, one example we fully discuss is that of ordered factorizations. While we recycle many of the concepts of Boltzmann random sampling, our samplers no longer obey a Boltzmann distribution; we thus have coined a new name for them: Dirichlet samplers. These are very efficient as they can generate objects of size n in O((log n)2) worst-case time complexity. By providing a means by which to generate very large random multiplicative objects, our Dirichlet samplers can facilitate the investigation of these interesting, yet little studied structures. We also hope to illustrate some of our general ideas regarding the future direction for random sampling.

AB - In 2001, Duchon, Flajolet, Louchard and Schaeffer introduced Boltzmann samplers, a radically novel way to efficiently generate huge random combinatorial objects without any preprocessing; the insight was that the probabilities can be obtained directly by evaluating the generating functions of combinatorials classes. Over the following decade, a vast array of papers has increased the formal expressiveness of these random samplers. Our paper introduces a new kind of sampler which generates multiplicative combinatorial structures, which enumerated by Dirichlet generating functions. Such classes, which are significantly harder to analyze than their additive counterparts, are at the intersection of combinatorics and analytic number theory. Indeed, one example we fully discuss is that of ordered factorizations. While we recycle many of the concepts of Boltzmann random sampling, our samplers no longer obey a Boltzmann distribution; we thus have coined a new name for them: Dirichlet samplers. These are very efficient as they can generate objects of size n in O((log n)2) worst-case time complexity. By providing a means by which to generate very large random multiplicative objects, our Dirichlet samplers can facilitate the investigation of these interesting, yet little studied structures. We also hope to illustrate some of our general ideas regarding the future direction for random sampling.

UR - http://www.scopus.com/inward/record.url?scp=84959912428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959912428&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84959912428

T3 - 9th Meeting on Analytic Algorithmics and Combinatorics 2012, ANALCO 2012

SP - 83

EP - 97

BT - 9th Meeting on Analytic Algorithmics and Combinatorics 2012, ANALCO 2012

PB - Society for Industrial and Applied Mathematics Publications

T2 - 9th Meeting on Analytic Algorithmics and Combinatorics, ANALCO 2012

Y2 - 16 January 2012

ER -