Galton-watson probability contraction

Moumanti Podder, Joel Spencer

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Article number20
JournalElectronic Communications in Probability
StatePublished - 2017


  • Almost sure theory
  • First order logic
  • Galton-Watson trees

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Galton-watson probability contraction'. Together they form a unique fingerprint.

Cite this