Alexis Darrasse ; Konstantinos Panagiotou ; Olivier Roussel ; Michele Soria - Biased Boltzmann samplers and generation of extended linear languages with shuffle

dmtcs:2989 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2989
Biased Boltzmann samplers and generation of extended linear languages with shuffleArticle

Authors: Alexis Darrasse 1; Konstantinos Panagiotou 2; Olivier Roussel 1; Michele Soria 1

  • 1 Algorithmes, Programmes et Résolution
  • 2 Max-Planck-Institut für Informatik

This paper is devoted to the construction of Boltzmann samplers according to various distributions, and uses stochastic bias on the parameter of a Boltzmann sampler, to produce a sampler with a different distribution for the size of the output. As a significant application, we produce Boltzmann samplers for words defined by regular specifications containing shuffle operators and linear recursions. This sampler has linear complexity in the size of the output, where the complexity is measured in terms of real-arithmetic operations and evaluations of generating functions.


Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: Boltzmann samplers,biased distributions,shuffle operator,combinatorial specifications,generating functions,random sampling,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 292 times.
This article's PDF has been downloaded 226 times.