A central limit theorem for additive functionals of increasing trees. (8th March 2019)

• Record Type: Journal Article
• Authors: Ralaivaosaona, Dimbinaina; Wagner, Stephan
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 4(2019)
• Page Start: 618
• Page End: 637
• Publication Date: 2019-03-08
• Subjects: Primary 60C05, -- Secondary 05C05, -- 60F05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000585
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: A tree functional is called additive if it satisfies a recursion of the form $F(T) = \sum_{j=1}^k F(B_j) + f(T)$, where B 1, …, Bk 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 generalized 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 other examples (old and new) are covered as well.