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 Σ, indexed by 1 ≤ j ≤ m, denote the finite set of equivalence classes arising out of this game, and D the set of all probability distributions over Σ. Let xj(c) denote the true probability of the class j ∈ Σ under Poisson(c) regime, and x(c) the true probability vector over all the equivalence classes. Then we are able to define a natural recursion function Γ, and a map Ψ = Ψc: D → D such that x(c) is a fixed point of Ψc, and starting with any distribution x ∈ D, we converge to this fixed point via Ψ because it is a contraction. We show this both for c ≤ 1 and c > 1, though the techniques for these two ranges are quite different.
Original language | English (US) |
---|---|
Article number | 20 |
Journal | Electronic Communications in Probability |
Volume | 22 |
DOIs | |
State | Published - 2017 |
Keywords
- Almost sure theory
- First order logic
- Galton-Watson trees
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty