Recursive functions on conditional Galton‐Watson trees. Issue 2 (10th April 2020)

• Record Type: Journal Article
• Authors: Broutin, Nicolas; Devroye, Luc; Fraiman, Nicolas
• Is Part Of: Random structures & algorithms. Volume 57:Issue 2(2020)
• Page Start: 304
• Page End: 316
• Publication Date: 2020-04-10
• Subjects: branching process -- probabilistic analysis of algorithms -- random Galton‐Watson tree -- recursive functions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20921
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .