Limiting distributions for additive functionals on Catalan trees

DOI10.1016/j.tcs.2004.05.010zbMath1071.68102arXivmath/0306226OpenAlexW2055711806MaRDI QIDQ703536

James Allen Fill, Nevin Kapur

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Central limit theoremDivide and conquerAdditive functionalsAiry distributionCatalan treesGeneralized polylogarithmHadamard product of functionsLimiting distributionsMethod of momentsShape functionalSingularity analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15) Combinatorics in computer science (68R05) Combinatorial probability (60C05)

Related Items (22)

Limit Theorems for Subtree Size Profiles of Increasing Trees ⋮ Central limit theorems for additive functionals and fringe trees in tries ⋮ Stochastic analysis of the extra clustering model for animal grouping ⋮ Limiting distributions for the number of inversions in labelled tree families ⋮ Central Limit Theorems for Additive Tree Parameters with Small Toll Functions ⋮ Analysis of a drop-push model for percolation and coagulation ⋮ Limit distributions for multitype branching processes of \(m\)-ary search trees ⋮ Precise logarithmic asymptotics for the right tails of some limit random variables for random trees ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ Limiting distributions for additive functionals on Catalan trees ⋮ The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance ⋮ Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees ⋮ A central limit theorem for additive functionals of increasing trees ⋮ A simple derivation of the mean of the Sackin index of tree balance under the uniform model on rooted binary labeled trees ⋮ Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees ⋮ The sum of powers of subtree sizes for conditioned Galton-Watson trees ⋮ Limit theorems for patterns in phylogenetic trees ⋮ Distinct fringe subtrees in random trees ⋮ Two results about the Sackin and Colless indices for phylogenetic trees and their shapes ⋮ The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees

Cites Work

• Limiting distributions for additive functionals on Catalan trees
• Conditional limit theorems for branching processes
• Singularity analysis and asymptotics of Bernoulli sums
• On binary search tree recursions with monomials as toll functions
• Singularity analysis, Hadamard products, and tree recurrences
• On a probability problem connected with railway traffic
• Phase changes in randomm-ary search trees and generalized quicksort
• A Gray Code for the Ideals of a Forest Poset
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Singularity Analysis of Generating Functions
• A complexity calculus for recursive tree algorithms
• A bernoulli excursion and its various applications
• On the log-product of the subtree-sizes of random trees
• The Wiener Index of simply generated random trees
• A limit theorem for “quicksort”
• Analytic variations on the Airy distribution
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Limiting distributions for additive functionals on Catalan trees