Recursive functions on conditional Galton‐Watson trees. Issue 2 (10th April 2020) - Broutin, Nicolas; Devroye, Luc; Fraiman, Nicolas
Abstract : A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element U . The value of the root is the key quantity of interest in general. In this study, all node values and function values are in a finite set S . In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on S, and the tree T n is a random Galton‐Watson tree of size n .