Central limit theorems for additive functionals and fringe trees in tries

DOI10.1214/22-EJP776zbMATH Open1492.60021WikidataQ113751958 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)