Central limit theorems for additive functionals and fringe trees in tries

DOI10.1214/22-EJP776zbMath1492.60021arXiv2003.02725WikidataQ113751958 ScholiaQ113751958MaRDI QIDQ2136104

Svante Janson

Publication date: 10 May 2022

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

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

zbMATH Keywords

asymptotic normalityadditive functionalsprotected nodesrandom tries

Mathematics Subject Classification ID

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

Related Items (1)

The sum of powers of subtree sizes for conditioned Galton-Watson trees

Cites Work

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

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