Recursive functions on conditional Galton--Watson trees

2018/05/23 by Broutin, Nicolas, Devroye, Luc, Fraiman, Nicolas
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1805.09425

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 first 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.

Related

• Minimax functions on Galton-Watson trees
• Constructing and searching conditioned Galton-Watson trees
• Simply generated trees, conditioned Galton--Watson trees, random allocations and condensation
• Conditioned Galton-Watson trees: The shape functional, and more on the sum of powers of subtree sizes and its mean
• Conditioned multi-type Galton-Watson trees