Central limit theorems for additive functionals and fringe trees in tries

DOI10.1214/22-EJP776MaRDI QIDQ2136104zbMATH OpenWikidataFDO

Authors 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

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

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$.

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

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 3139051 (Why is no real title available?)
• scientific article; zbMATH DE number 3141365 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A probabilistic analysis of some tree algorithms
• Additive tree functionals with small toll functions and subtrees of random trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Analytic combinatorics
• Asymptotic distribution of two-protected nodes in random binary search trees
• Asymptotic fringe distributions for general families of random trees
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Central limit theorems for additive tree parameters with small toll functions
• Digital trees and memoryless sources: from arithmetics to analysis
• Estimates of moments of infinite-dimensional martingales
• Exact Rosenthal-type bounds
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Limiting distributions for additive functionals on Catalan trees
• Monotonicity, asymptotic normality and vertex degrees in random graphs
• New results on the size of tries
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• On the log-product of the subtree-sizes of random trees
• Probability: a graduate course
• Protected nodes and fringe subtrees in some random trees
• Random Trees
• Renewal theory in the analysis of tries and strings
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Stochastic Monotonicity and Conditioning in the Limit
• k-protected vertices in binary search trees

Cited in

(5)

• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• 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)