A note on limits of sequences of binary trees
From MaRDI portal
Publication:6131798
DOI10.46298/DMTCS.10968arXiv2302.07850MaRDI QIDQ6131798
Author name not available (Why is that?)
Publication date: 18 April 2024
Published in: (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2302.07850
No records found.
No records found.
This page was built for publication: A note on limits of sequences of binary trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131798)
