Efficient random sampling of binary and unary-binary trees via holonomic\n equations

2014/01/06 by Axel Bacher, Olivier Bodini, Bacher, Axel +3
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1401.1140

openalex publication_date 2014/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a new uniform random sampler for binary trees with n internal\nnodes consuming 2n + \Θ(\log(n)²) random bits on average. This makes it\nquasi-optimal and out-performs the classical Remy algorithm. We also present a\nsampler for unary-binary trees with n nodes taking \Θ(n) random bits on\naverage. Both are the first linear-time algorithms to be optimal up to a\nconstant.\n

Related

• Holonomic equations and efficient random generation of binary trees
• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and Applications
• Exact-size Sampling of Enriched Trees in Linear Time
• An algorithm for generating random mixed-arity trees
• Massively Parallel Construction of Radix Tree Forests for the Efficient Sampling of Discrete Probability Distributions