Galton-Watson probability contraction

DOI10.1214/17-ECP47zbMATH Open1360.60157arXiv1512.07371MaRDI QIDQ516101FDOQ516101

Authors: Moumanti Podder, Joel Spencer 

Publication date: 21 March 2017

Published in: Electronic Communications in Probability (Search for Journal in Brave)

Abstract: We are concerned with exploring the probabilities of first order statements for Galton-Watson trees with $Poisson(c)$ offspring distribution. Fixing a positive integer $k$, we exploit the $k$-move Ehrenfeucht game on rooted trees for this purpose. Let $Sigma$, indexed by $1leqjleqm$, denote the finite set of equivalence classes arising out of this game, and $D$ the set of all probability distributions over $Sigma$. Let $x_j(c)$ denote the true probability of the class $jinSigma$ under $Poisson(c)$ regime, and $vecx(c)$ the true probability vector over all the equivalence classes. Then we are able to define a natural recursion function $Gamma$, and a map $Psi=Ps{i}_c:DightarrowD$ such that $vecx(c)$ is a fixed point of $Ps{i}_c$, and starting with any distribution $vecxinD$, we converge to this fixed point via $Psi$ because it is a contraction. We show this both for $cleq1$ and $c>1$, though the techniques for these two ranges are quite different.

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

Recommendations

• First order probabilities for Galton-Watson trees
• Random tree recursions: Which fixed points correspond to tangible sets of trees?
• On the number of vertices with a given degree in a Galton-Watson tree
• Estimates of the extinction probability of the Galton-Watson process
• Galton-Watson trees with vanishing martingale limit

zbMATH Keywords

almost sure theoryfirst-order logicGalton-Watson trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cited In (4)

• Continuous phase transitions on Galton–Watson trees
• Analyticity for rapidly determined properties of Poisson Galton-Watson trees
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• First order probabilities for Galton-Watson trees

This page was built for publication: Galton-Watson probability contraction

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