Recursive functions on conditional Galton‐Watson trees
| Autor: | Nicolas Broutin, Nicolas Fraiman, Luc Devroye |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Distribution (number theory)
Applied Mathematics General Mathematics Value (computer science) Random element 0102 computer and information sciences Function (mathematics) 01 natural sciences Computer Graphics and Computer-Aided Design Combinatorics 010201 computation theory & mathematics Limit (mathematics) Tree (set theory) Finite set Software Branching process Mathematics |
| Zdroj: | Random Structures & Algorithms. 57:304-316 |
| ISSN: | 1098-2418 1042-9832 |
| DOI: | 10.1002/rsa.20921 |
| Popis: | 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$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text