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

DOI10.1016/J.TCS.2017.07.009MaRDI QIDQ2402673zbMATH OpenOpenAlexFDO

Authors Axel Bacher, Olivier Bodini, Alice Jacquot

Publication date 13 September 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.1140

zbMATH Keywords

holonomic equationplane treesrandom samplingRemy algorithm

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We present a new uniform random sampler for binary trees with $n$ internal nodes consuming $2n+Theta(log(n{)}^2)$ random bits on average. This makes it quasi-optimal and out-performs the classical Remy algorithm. We also present a sampler for unary-binary trees with $n$ nodes taking $Theta(n)$ random bits on average. Both are the first linear-time algorithms to be optimal up to a constant.

Recommendations

• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• Generating random binary trees -- a survey
• The generation of binary trees as a numerical problem
• Generating binary trees at random
• The generation of random, binary unordered trees

Cites work

• A calculus for the random generation of labelled combinatorial structures
• A linear-time algorithm for the generation of trees
• A Mathematical Theory of Communication
• Analytic combinatorics
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• GFUN
• scientific article; zbMATH DE number 3900794 (Why is no real title available?)
• Multi-dimensional Boltzmann sampling of languages
• On Buffon machines and numbers
• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• The random generation of underdiagonal walks
• Uniform generation of a Motzkin word

Cited in

(10)

• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• Complexity of anticipated rejection algorithms and the Darling-Mandelbrot distribution
• Exact-size sampling for Motzkin trees in linear time via Boltzmann samplers and holonomic specification
• Sampling planar tanglegrams and pairs of disjoint triangulations
• Holonomic equations and efficient random generation of binary trees
• The degree Gini index of several classes of random trees and their poissonized counterparts -- evidence for duality
• Optimal generation of strictly increasing binary trees and beyond
• Simple random sampling of binary forests with fixed number of nodes and trees
• Simple random sampling of binary forests with fixed number of nodes and trees
• Where do (random) trees grow leaves?

Describes a project that uses

Uses Software

• gfun

This page was built for publication: Efficient random sampling of binary and unary-binary trees via holonomic equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402673)