Uniform random generations and rejection method(I) with binomial majorant

2023/03/16 by Laurent Alonso, Alonso, Laurent
Computer Science · Mathematics · #Algorithms and Data Compression #Advanced Combinatorial Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2303.09338

Abstract

We present three simple algorithms to uniformly generate `Fibonacci words' (i.e., some words that are enumerated by Fibonacci numbers), Schröder trees of size n and Motzkin left factors of size n and final height h. These algorithms have an average complexity of O(n) in the unit-cost RAM model.

Related

• Optimal Discrete Uniform Generation from Coin Flips, and Applications
• Holonomic equations and efficient random generation of binary trees
• Non-redundant random generation algorithms for weighted context-free\n languages
• Golden and Alternating, fast simple O(lg n) algorithms for Fibonacci
• A portable uniform random number generator well suited for the rejection method