Rudolf Grübel - A note on limits of sequences of binary trees

dmtcs:10968 - Discrete Mathematics & Theoretical Computer Science, May 30, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.10968
A note on limits of sequences of binary treesArticle

Authors: Rudolf Grübel

    We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the set of possible limits and its structure as a metric space. For random trees the subtree size topology arises in the context of algorithms for searching and sorting when applied to random input, resulting in a sequence of nested trees. For these we obtain a structural result based on a local version of exchangeability. This in turn leads to a central limit theorem, with possibly mixed asymptotic normality.


    Volume: vol. 25:1
    Section: Analysis of Algorithms
    Published on: May 30, 2023
    Accepted on: May 11, 2023
    Submitted on: February 16, 2023
    Keywords: Mathematics - Combinatorics,Mathematics - Probability,05C05, 60C05, 68W40

    Consultation statistics

    This page has been seen 421 times.
    This article's PDF has been downloaded 323 times.