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 $1 leq j leq m$, 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 $j in Sigma$ under $Poisson(c)$ regime, and $vec{x}(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 = Psi_{c}: D rightarrow D$ such that $vec{x}(c)$ is a fixed point of $Psi_{c}$, and starting with any distribution $vec{x} in D$, we converge to this fixed point via $Psi$ because it is a contraction. We show this both for $c leq 1$ and $c > 1$, though the techniques for these two ranges are quite different.
Download