Central limit theorems for additive functionals and fringe trees in tries

DOI10.1214/22-EJP776zbMATH Open1492.60021arXiv2003.02725WikidataQ113751958 ScholiaQ113751958MaRDI QIDQ2136104FDOQ2136104

Authors: Svante Janson 

Publication date: 10 May 2022

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: We give general theorems on asymptotic normality for additive functionals of random tries generated by a sequence of independent strings. These theorems are applied to show asymptotic normality of the distribution of random fringe trees in a random trie. Formulas for asymptotic mean and variance are given. In particular, the proportion of fringe trees of size $k$ (defined as number of keys) is asymptotically, ignoring oscillations, $c/(k(k-1))$ for $kge2$, where $c=1/(1+H)$ with $H$ the entropy of the digits. Another application gives asymptotic normality of the number of $k$-protected nodes in a random trie. For symmetric tries, it is shown that the asymptotic proportion of $k$-protected nodes (ignoring oscillations) decreases geometrically as $koinfty$.

Full work available at URL: https://arxiv.org/abs/2003.02725

Recommendations

• A central limit theorem for additive functionals of increasing trees
• A central limit theorem for almost local additive tree functionals
• Central limit theorems for additive tree parameters with small toll functions
• On central limit theory for random additive functions under weak dependence restrictions
• scientific article; zbMATH DE number 431868
• Central limit theorem for stochastically additive functionals of ergodic chains
• A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees

zbMATH Keywords

asymptotic normalityadditive functionalsprotected nodesrandom tries

Mathematics Subject Classification ID

Trees (05C05) Central limit and other weak theorems (60F05) Data structures (68P05) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Analytic combinatorics
• Title not available (Why is that?)
• Random Trees
• Title not available (Why is that?)
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Probability: A Graduate Course
• Exact Rosenthal-type bounds
• Title not available (Why is that?)
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Limiting distributions for additive functionals on Catalan trees
• Asymptotic fringe distributions for general families of random trees
• \(k\)-protected vertices in binary search trees
• Asymptotic distribution of two-protected nodes in random binary search trees
• Protected nodes and fringe subtrees in some random trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Title not available (Why is that?)
• Monotonicity, asymptotic normality and vertex degrees in random graphs
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• A probabilistic analysis of some tree algorithms
• New results on the size of tries
• Additive tree functionals with small toll functions and subtrees of random trees
• On the log-product of the subtree-sizes of random trees
• Central Limit Theorems for Additive Tree Parameters with Small Toll Functions
• Renewal theory in the analysis of tries and strings
• Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees
• Estimates of moments of infinite-dimensional martingales
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• Stochastic Monotonicity and Conditioning in the Limit

Cited In (4)

• A central limit theorem for almost local additive tree functionals
• Limiting distributions for additive functionals on Catalan trees
• The sum of powers of subtree sizes for conditioned Galton-Watson trees
• A central limit theorem for additive functionals of increasing trees

This page was built for publication: Central limit theorems for additive functionals and fringe trees in tries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136104)