Random tree recursions: Which fixed points correspond to tangible sets of trees?. Issue 3 (14th November 2019)

• Record Type: Journal Article
• Authors: Johnson, Tobias; Podder, Moumanti; Skerman, Fiona
• Is Part Of: Random structures & algorithms. Volume 56:Issue 3(2020)
• Page Start: 796
• Page End: 837
• Publication Date: 2019-11-14
• Subjects: endogeny -- fixed point -- Galton‐Watson tree -- interpretation -- recursive distributional equation -- tree automaton; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20895
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Let B be the set of rooted trees containing an infinite binary subtree starting at the root. This set satisfies the metaproperty that a tree belongs to it if and only if its root has children u and v such that the subtrees rooted at u and v belong to it. Let p be the probability that a Galton‐Watson tree falls in B . The metaproperty makes p satisfy a fixed‐point equation, which can have multiple solutions. One of these solutions is p, but what is the meaning of the others? In particular, are they probabilities of the Galton‐Watson tree falling into other sets satisfying the same metaproperty? We create a framework for posing questions of this sort, and we classify solutions to fixed‐point equations according to whether they admit probabilistic interpretations. Our proofs use spine decompositions of Galton‐Watson trees and the analysis of Boolean functions.