Limiting distributions for additive functionals on Catalan trees

DOI10.1016/J.TCS.2004.05.010zbMATH Open1071.68102arXivmath/0306226OpenAlexW2055711806MaRDI QIDQ703536FDOQ703536

Authors: James Allen Fill, Nevin Kapur 

Publication date: 11 January 2005

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

Abstract: Additive tree functionals represent the cost of many divide-and-conquer algorithms. We derive the limiting distribution of the additive functionals induced by toll functions of the form (a) n^alpha when alpha > 0 and (b) log n (the so-called shape functional) on uniformly distributed binary search trees, sometimes called Catalan trees. The Gaussian law obtained in the latter case complements the central limit theorem for the shape functional under the random permutation model. Our results give rise to an apparently new family of distributions containing the Airy distribution (alpha = 1) and the normal distribution [case (b), and case (a) as $alphadownarrow0$]. The main theoretical tools employed are recent results relating asymptotics of the generating functions of sequences to those of their Hadamard product, and the method of moments.

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

Recommendations

• A central limit theorem for additive functionals of increasing trees
• A central limit theorem for almost local additive tree functionals
• scientific article; zbMATH DE number 1880255
• Additive functionals of $d$-ary increasing trees
• Central limit theorems for additive functionals and fringe trees in tries
• Additive tree functionals with small toll functions and subtrees of random trees
• A functional limit theorem for the profile of random recursive trees
• A functional limit theorem for the profile of \(b\)-ary trees
• Limit theorems for functionals of recursive trees.
• Central limit theorems for additive tree parameters with small toll functions

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

• A repertoire for additive functionals of uniformly distributed \(m\)-ary search trees
• Two results about the Sackin and Colless indices for phylogenetic trees and their shapes
• Cost functionals for large (uniform and simply generated) random trees
• Conditioned Galton-Watson trees: the shape functional, and more on the sum of powers of subtree sizes and its mean
• The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees
• A central limit theorem for almost local additive tree functionals
• On \(q\)-functional equations and excursion moments
• Stochastic analysis of the extra clustering model for animal grouping
• Central limit theorems for additive tree parameters with small toll functions
• Limiting distributions for additive functionals on Catalan trees
• Central limit theorems for additive functionals and fringe trees in tries
• The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
• Analysis of a drop-push model for percolation and coagulation
• Singularity analysis, Hadamard products, and tree recurrences
• Additive tree functionals with small toll functions and subtrees of random trees
• A simple derivation of the mean of the Sackin index of tree balance under the uniform model on rooted binary labeled trees
• The sum of powers of subtree sizes for conditioned Galton-Watson trees
• Distinct fringe subtrees in random trees
• Limiting distributions for the number of inversions in labelled tree families
• A central limit theorem for additive functionals of increasing trees
• Limit theorems for patterns in phylogenetic trees
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• Limit distributions for multitype branching processes of \(m\)-ary search trees
• Limit theorems for subtree size profiles of increasing trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703536)