Random Generation Using Binomial Approximations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2010

Random Generation Using Binomial Approximations

Résumé

Generalizing an idea used by Alonso to generate uniformly at random Motzkin words, we outline an approach to build efficient random generators using binomial distributions and rejection algorithms. As an application of this method, we present random generators, both efficient and easy to implement, for partial injections and colored unary-binary trees.
Fichier principal
Vignette du fichier
dmAM0125.pdf (361.45 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01185570 , version 1 (20-08-2015)

Identifiants

Citer

Dominique Gouyou-Beauchamps, Cyril Nicaud. Random Generation Using Binomial Approximations. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.359-372, ⟨10.46298/dmtcs.2772⟩. ⟨hal-01185570⟩
319 Consultations
1582 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More