The sum of powers of subtree sizes for conditioned Galton-Watson trees

DOI10.1214/22-EJP831MaRDI QIDQ2082709zbMATH OpenOpenAlexFDO

Authors James Allen Fill, Svante Janson

Publication date 4 October 2022

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

Full work available at URL https://arxiv.org/abs/2104.02715, https://projecteuclid.org/journals/electronic-journal-of-probability/volume-27/issue-none/The-sum-of-powers-of-subtree-sizes-for-conditioned-GaltonWatson/10.1214/22-EJP831.full

zbMATH Keywords

additive functionalBrownian excursionconditioned Galton-Watson treegenerating functionHadamard product of sequencesmethod of momentspolylogarithmrandom analytic functionsimply generated random treesingularity analysissubtree sizestree recurrence

Mathematics Subject Classification ID

Trees (05C05) Miscellaneous topics of analysis in the complex plane (30E99) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We study the additive functional $X_n(alpha)$ on conditioned Galton-Watson trees given, for arbitrary complex $alpha$, by summing the $alpha$th power of all subtree sizes. Allowing complex $alpha$ is advantageous, even for the study of real $alpha$, since it allows us to use powerful results from the theory of analytic functions in the proofs. For $Realpha<0$, we prove that $X_n(alpha)$, suitably normalized, has a complex normal limiting distribution; moreover, as processes in $alpha$, the weak convergence holds in the space of analytic functions in the left half-plane. We establish, and prove similar process-convergence extensions of, limiting distribution results for $alpha$ in various regions of the complex plane. We focus mainly on the case where $Realpha>0$, for which $X_n(alpha)$, suitably normalized, has a limiting distribution that is not normal but does not depend on the offspring distribution $xi$ of the conditioned Galton-Watson tree, assuming only that $E[xi]=1$ and $0<mathrmVar[xi]<infty$. Under a weak extra moment assumption on $xi$, we prove that the convergence extends to moments, ordinary and absolute and mixed, of all orders. At least when $Realpha>frac12$, the limit random variable $Y(alpha)$ can be expressed as a function of a normalized Brownian excursion.

Recommendations

• Non-fringe subtrees in conditioned Galton-Watson trees
• A limit theorem for the contour process of conditioned Galton-Watson trees
• Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees

Cites work

• A bernoulli excursion and its various applications
• A central limit theorem for additive functionals of increasing trees
• Analytic combinatorics
• Analytic variations on the Airy distribution
• Asymptotic distribution for the cost of linear probing hashing
• Asymptotic fringe distributions for general families of random trees
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Central limit theorems for additive functionals and fringe trees in tries
• Central limit theorems for additive tree parameters with small toll functions
• Cost functionals for large (uniform and simply generated) random trees
• Enumerating graphs and Brownian motion
• Gaussian Hilbert Spaces
• Generalized gamma convolutions and related classes of distributions and densities
• Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 3137662 (Why is no real title available?)
• scientific article; zbMATH DE number 3861550 (Why is no real title available?)
• scientific article; zbMATH DE number 3680123 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 3504209 (Why is no real title available?)
• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 1349990 (Why is no real title available?)
• scientific article; zbMATH DE number 1022519 (Why is no real title available?)
• scientific article; zbMATH DE number 2031102 (Why is no real title available?)
• scientific article; zbMATH DE number 852055 (Why is no real title available?)
• scientific article; zbMATH DE number 3272562 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Kac's formula, levy's local time and brownian excursion
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Limiting distributions for additive functionals on Catalan trees
• NIST handbook of mathematical functions
• Normal convergence problem? Two moments and a recurrence may be the clues
• On the Accuracy of Gaussian Approximation to the Distribution Functions of Sums of Independent Variables
• On the Altitude of Nodes in Random Trees
• On the analysis of linear probing hashing
• On the log-product of the subtree-sizes of random trees
• On the total heights of random rooted binary trees
• On the total heights of random rooted trees
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• Probability: a graduate course
• Random cutting and records in deterministic and random trees
• Random Trees
• Random trees and applications
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Singularity analysis and asymptotics of Bernoulli sums
• Singularity analysis, Hadamard products, and tree recurrences
• The Brownian excursion area: A numerical analysis
• The continuum random tree. III
• The density of the ISE and local limit laws for embedded trees
• The Multiplicative Process
• The Wiener Index of simply generated random trees
• Transfer theorems and asymptotic distributional results for m‐ary search trees

Cited in

(5)

• Non-fringe subtrees in conditioned Galton-Watson trees
• The Horton-Strahler number of conditioned Galton-Watson trees
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• Corrigendum to: ``The sum of powers of subtree sizes for conditioned Galton-Watson trees
• Conditioned Galton-Watson trees: the shape functional, and more on the sum of powers of subtree sizes and its mean

Describes a project that uses

Uses Software

• DLMF

This page was built for publication: The sum of powers of subtree sizes for conditioned Galton-Watson trees

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