Random tree recursions: Which fixed points correspond to tangible sets of trees?

Tobias Johnson*, Moumanti Podder, Fiona Skerman

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

2 Citations (Scopus)
6 Downloads (Pure)

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.
Original languageEnglish
Number of pages42
JournalRandom Structures and Algorithms
Early online date14 Nov 2019
DOIs
Publication statusE-pub ahead of print - 14 Nov 2019

Keywords

  • endogeny
  • tree automaton
  • fixed point
  • Galton-Watson tree
  • interpretation
  • recursive distributional equation

Fingerprint Dive into the research topics of 'Random tree recursions: Which fixed points correspond to tangible sets of trees?'. Together they form a unique fingerprint.

Cite this