Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis
Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
SIAM
Abstract
For fixed t ≥ 2, we consider the class of representations of 1 as a sum of unit fractions
whose denominators are powers of t, or equivalently the class of canonical compact t-ary Huffman
codes, or equivalently rooted t-ary plane “canonical” trees. We study the probabilistic behavior of
the height (limit distribution is shown to be normal), the number of distinct summands (normal
distribution), the path length (normal distribution), the width (main term of the expectation and
concentration property), and the number of leaves at maximum distance from the root (discrete
distribution).
Description
CITATION: Heuberger, C., Krenn, D. & Wagner, S. 2015. Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis. SIAM Journal on Discrete Mathematics, 29(3):1600–1653, doi:10.1137/15M1017107.
The original publication is available at http://epubs.siam.org/journal/sjdmec
The original publication is available at http://epubs.siam.org/journal/sjdmec
Keywords
Canonical t-ary trees, Compact prefix-free codes, Unit fractions, Limit theorems (Probability theory), Canonical correlation (Statistics), Huffman codes
Citation
Heuberger, C., Krenn, D. & Wagner, S. 2015. Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis. SIAM Journal on Discrete Mathematics, 29(3):1600–1653, doi:10.1137/15M1017107.