Limiting distributions for additive functionals on Catalan trees
From MaRDI portal
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 ]. 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.
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
Cites work
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- scientific article; zbMATH DE number 1984556 (Why is no real title available?)
- scientific article; zbMATH DE number 765034 (Why is no real title available?)
- scientific article; zbMATH DE number 852055 (Why is no real title available?)
- scientific article; zbMATH DE number 3211688 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- A Gray Code for the Ideals of a Forest Poset
- A bernoulli excursion and its various applications
- A complexity calculus for recursive tree algorithms
- A limit theorem for “quicksort”
- Analytic variations on the Airy distribution
- Conditional limit theorems for branching processes
- Limiting distributions for additive functionals on Catalan trees
- On a probability problem connected with railway traffic
- On binary search tree recursions with monomials as toll functions
- On the log-product of the subtree-sizes of random trees
- Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
- Phase changes in random \(m\)-ary search trees and generalized quicksort
- Singularity Analysis of Generating Functions
- Singularity analysis and asymptotics of Bernoulli sums
- Singularity analysis, Hadamard products, and tree recurrences
- The Wiener Index of simply generated random trees
Cited in
(28)- A central limit theorem for additive functionals of increasing trees
- Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
- A central limit theorem for almost local additive tree functionals
- Singularity analysis, Hadamard products, and tree recurrences
- Additive tree functionals with small toll functions and subtrees of random trees
- A repertoire for additive functionals of uniformly distributed \(m\)-ary search trees
- Cost functionals for large (uniform and simply generated) random trees
- Limiting distributions for the number of inversions in labelled tree families
- Limiting distributions for additive functionals on Catalan trees
- Central limit theorems for additive tree parameters with small toll functions
- Central limit theorems for additive functionals and fringe trees in tries
- On \(q\)-functional equations and excursion moments
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance
- Stochastic analysis of the extra clustering model for animal grouping
- Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
- Additive functionals of \(d\)-ary increasing trees
- The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees
- Limit distributions for multitype branching processes of \(m\)-ary search trees
- Two results about the Sackin and Colless indices for phylogenetic trees and their shapes
- Limit theorems for subtree size profiles 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
- Conditioned Galton-Watson trees: the shape functional, and more on the sum of powers of subtree sizes and its mean
- The sum of powers of subtree sizes for conditioned Galton-Watson trees
- Limit theorems for patterns in phylogenetic trees
- Analysis of a drop-push model for percolation and coagulation
- Cost functionals for large random trees
- Distinct fringe subtrees in random 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)
