Advanced search

Browse by subject

Browse by provider

Browse by language

Content Details
Normal View
CIP View

Efficient random sampling of binary and ...

Bacher, Axel...

Free

Share this content

Efficient random sampling of binary and unary-binary trees via holonomic equations by Bacher, Axel ( Author )

Content Provider	Lemonjar Open Access
Publisher	Australian National University
Publication Date	01-09-2023
Summary	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.
ISBN	-
Item Type	Article
File Type	pdf
File Size	29.34 KB
Language	English
Subjects	-
Unlimited	MYR 0.01
Total read	-
URL	http://arxiv.org/abs/1401.1140

Citation

Review the full bibliography data and make any necessary corrections before using. Always consult your library resources for the exact formatting and punctuation guidelines.

AMA 11th EditionReferences

Bacher, Axel. Efficient random sampling of binary and unary-binary trees via holonomic equations. Australian National University. September 01, 2023. Accessed September 20, 2024. https://online.provdatabase.com/cite/23002

APA 7th EditionReferences

Bacher, Axel. (2023). Efficient random sampling of binary and unary-binary trees via holonomic equations. Australian National University. https://online.provdatabase.com/cite/23002

Chicago 17th EditionReferences

Bacher, Axel. Efficient random sampling of binary and unary-binary trees via holonomic equations. Australian National University. 2023. https://online.provdatabase.com/cite/23002

HarvardReferences

Bacher, Axel. (2023). Efficient random sampling of binary and unary-binary trees via holonomic equations. [Online]. Australian National University. Available from: https://online.provdatabase.com/cite/23002. (Accessed 20 September 2024).

Harvard AustraliaReferences

Bacher, Axel, 2023, Efficient random sampling of binary and unary-binary trees via holonomic equations, Australian National University, viewed 20 September 2024, <https://online.provdatabase.com/cite/23002>

MLA 9th EditionWorks Cited

Bacher, Axel. Efficient random sampling of binary and unary-binary trees via holonomic equations. Australian National University, 2023. PROV Database, https://online.provdatabase.com/cite/23002.

Share this eBook