Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and Applications

2014/01/19 by Olivier Bodini, Bodini, Olivier, Julien David +5
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1401.4712

19 pages

arxiv created 2014/01/19 · openalex publication_date 2014/01/19 · arxiv updated 2014/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we redesign and simplify an algorithm due to Remy et al. for the generation of rooted planar trees that satisfies a given partition of degrees. This new version is now optimal in terms of random bit complexity, up to a multiplicative constant. We then apply a natural process "simulate-guess-and-proof" to analyze the height of a random Motzkin in function of its frequency of unary nodes. When the number of unary nodes dominates, we prove some unconventional height phenomenon (i.e. outside the universal square root behaviour.)

Related

• Efficient random sampling of binary and unary-binary trees via holonomic\n equations
• Universal height and width bounds for random trees
• Tail bounds for the height and width of a random tree with a given degree sequence
• Random trees have height O(√(n))
• Tight universal bounds on the height times the width of random trees