Additive functionals of d-ary increasing trees

MaRDI QIDQ4632497zbMATH OpenFDO

Authors Dimbinaina Ralaivaosaona, Stephan Wagner

Publication date 29 April 2019

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

zbMATH Keywords

central limit theoremautomorphismsrandom treesincreasing treesadditive tree functional

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Analysis of algorithms (68W40) Data structures (68P05) Combinatorial probability (60C05)

Abstract: A tree functional is called additive if it satisfies a recursion of the form $F(T)=su{m}_{j=1}^{k}F(B_j)+f(T)$, where $B_1,ldots,B_k$ are the branches of the tree $T$ and $f(T)$ is a toll function. We prove a general central limit theorem for additive functionals of $d$-ary increasing trees under suitable assumptions on the toll function. The same method also applies to generalised plane-oriented increasing trees (GPORTs). One of our main applications is a log-normal law that we prove for the size of the automorphism group of $d$-ary increasing trees, but many other examples (old and new) are covered as well.

Recommendations

• A central limit theorem for additive functionals of increasing trees
• A central limit theorem for almost local additive tree functionals
• Central limit theorems for additive tree parameters with small toll functions
• Additive tree functionals with small toll functions and subtrees of random trees
• Limiting distributions for additive functionals on Catalan trees

Cited in

(6)

• Central limit theorems for additive tree parameters with small toll functions
• Limiting distributions for additive functionals on Catalan trees
• Asymptotic normality of almost local functionals in conditioned Galton-Watson trees
• Additive tree functionals with small toll functions and subtrees of random trees
• A decreasing rearrangement for functions on homogeneous trees
• A central limit theorem for additive functionals of increasing trees

This page was built for publication: Additive functionals of \(d\)-ary increasing trees

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