Cost functionals for large (uniform and simply generated) random trees

DOI10.1214/18-EJP213zbMath1398.05061OpenAlexW2963439863MaRDI QIDQ1990219

Marion Sciauveau, Jean-François Delmas, Jean-Stéphane Dhersin

Publication date: 25 October 2018

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.ejp/1536717746

zbMATH Keywords

cost functionalBrownian excursioncontinuum random treerandom binary treetoll function

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Functional limit theorems; invariance principles (60F17)

Related Items

Zooming in at the root of the stable tree ⋮ A graphon counter example ⋮ Protection numbers in simply generated trees and Pólya 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new balance index for phylogenetic trees
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• Limiting distributions for additive functionals on Catalan trees
• Local limits of conditioned Galton-Watson trees: the condensation case
• The continuum random tree. I
• Asymptotic fringe distributions for general families of random trees
• Random trees and applications
• The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance
• On \(q\)-functional equations and excursion moments
• Arbres et processus de Galton-Watson. (Trees and Galton-Watson processes)
• Branching processes in Lévy processes: The exploration process
• The uniform random tree in a Brownian excursion
• On the total heights of random rooted binary trees
• A limit theorem for the contour process of conditioned Galton-Watson trees
• On binary search tree recursions with monomials as toll functions
• Singularity analysis, Hadamard products, and tree recurrences
• The center of mass of the ISE and the Wiener index of trees
• Probabilistic and fractal aspects of Lévy trees
• The contraction method for recursive algorithms
• Limit theorems for conditioned non-generic Galton-Watson trees
• The continuum random tree. III
• Exact formulas for the variance of several balance indices under the Yule model
• The forest associated with the record process on a Lévy tree
• Probability and real trees. Ecole d'Eté de Probabilités de Saint-Flour XXXV -- 2005. Lecture given at the Saint-Flour probability summer school, July 6--23, 2005.
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Local limits of conditioned Galton-Watson trees: the infinite spine case
• Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees
• A Simple Proof of Duquesne’s Theorem on Contour Processes of Conditioned Galton–Watson Trees
• Record process on the Continuum Random Tree
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• On the distribution of subtree orders of a tree
• Some Elementary Inequalities Relating to the Gamma and Incomplete Gamma Function
• Limiting Distributions for Path Lengths in Recursive Trees
• A limiting distribution for quicksort
• The Galton-Watson process conditioned on the total progeny
• The Wiener Index of simply generated random trees
• Total Path Length for Random Recursive Trees
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Asymptotic cost of cutting down random free trees
• Transfer theorems and asymptotic distributional results for m‐ary search trees
• Central Limit Theorems for Additive Tree Parameters with Small Toll Functions
• A limit theorem for “quicksort”
• Wiener index of trees: Theory and applications