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

DOI10.1002/RSA.20895zbMATH Open1445.05028arXiv1808.03019OpenAlexW3106318087WikidataQ126797466 ScholiaQ126797466MaRDI QIDQ5113956FDOQ5113956

Tobias Johnson, Moumanti Podder, Fiona Skerman

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Let $mathcalB$ 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 $mathcalB$. 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.

Full work available at URL: https://arxiv.org/abs/1808.03019

Recommendations

• Random recursive trees: a boundary theory approach
• Branches in random recursive \(k\)-Ary trees
• Recursive construction of continuum random trees
• scientific article; zbMATH DE number 3935066
• scientific article
• scientific article; zbMATH DE number 426362
• On tail bounds for random recursive trees
• Random Trees
• On the structure of random plane‐oriented recursive trees and their branches

zbMATH Keywords

interpretationfixed pointGalton-Watson treetree automatonendogenyrecursive distributional equation

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Infinite graphs (05C63) Boolean functions (06E30)

Cited In (5)

• Galton-Watson trees with the same mean have the same polar sets
• Continuous phase transitions on Galton–Watson trees
• Galton–Watson games
• Recursive tree processes and the mean-field limit of stochastic flows
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves

This page was built for publication: Random tree recursions: Which fixed points correspond to tangible sets of trees?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113956)