Galton-Watson probability contraction. (English) Zbl 1360.60157

Podder, Moumanti; Spencer, Joel

Electron. Commun. Probab. 22, Paper No. 20, 16 p. (2017).

Summary: We are concerned with exploring the probabilities of first order statements for Galton-Watson trees with \(\mathrm{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 \(\mathrm{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.

MSC:

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

Keywords:

Galton-Watson trees; almost sure theory; first-order logic