Additive functionals of $d$-ary increasing trees

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,\dots ,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.

Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Kraków, Poland, 4-8 July 2016