Browsing by Author "Heuberger, Clemens"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Application of Smirnov words to waiting time distributions of runs
    (Electronic Journal of Combinatorics, 2017) Freiberg, Uta; Heuberger, Clemens; Prodinger, Helmut
    Consider infinite random words over a finite alphabet where the letters occur as an i.i.d. sequence according to some arbitrary distribution on the alphabet. The expectation and the variance of the waiting time for the first completed h-run of any letter (i.e., first occurrence of h subsequential equal letters) is computed. The expected waiting time for the completion of h-runs of j arbitrary distinct letters is also given.
  • Thumbnail Image
    Item
    Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis
    (SIAM, 2015) Heuberger, Clemens; Krenn, Daniel; Wagner, Stephan
    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).
  • Thumbnail Image
    Item
    Protection number in plane trees
    (University of Belgrade - School of Electrical Engineering, 2017-10) Heuberger, Clemens; Prodinger, Helmut
    The protection number of a plane tree is the minimal distance of the root to a leaf; this definition carries over to an arbitrary node in a plane tree by considering the maximal subtree having this node as a root. We study the the protection number of a uniformly chosen random tree of size n and also the protection number of a uniformly chosen node in a uniformly chosen random tree of size n. The method is to apply singularity analysis to appropriate generating functions. Additional results are provided as well.