Galton-Watson probability contraction

DOI10.1214/17-ECP47MaRDI QIDQ516101zbMATH OpenFDO

Authors Moumanti Podder, Joel Spencer

Publication date 21 March 2017

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

Full work available at URL https://arxiv.org/abs/1512.07371, https://projecteuclid.org/euclid.ecp/1489651213

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)

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.

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

Cited in

(4)

• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Analyticity for rapidly determined properties of Poisson Galton-Watson trees
• First order probabilities for Galton-Watson trees
• Continuous phase transitions on 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)