Central limit theorems for additive functionals and fringe trees in tries

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

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

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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random Trees
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Probability: A Graduate Course
• Exact Rosenthal-type bounds
• 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
• 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

Recommendations

• Title not available (Why is that?) 👍 👎
• Central limit theorem for stochastically additive functionals of ergodic chains 👍 👎
• On central limit theory for random additive functions under weak dependence restrictions 👍 👎
• A central limit theorem for almost local additive tree functionals 👍 👎
• A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees 👍 👎
• A central limit theorem for additive functionals of increasing trees 👍 👎
• Central Limit Theorems for Additive Tree Parameters with Small Toll Functions 👍 👎

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)