Galton-Watson process

A Galton--Watson process forms each generation by giving every current individual an independent number of offspring with a common distribution.

In a Galton-Watson process, each individual independently has $j$ children with probability $p_j$. This probability distribution determines its offspring probability generating function, its mean $f^{\prime }(1)$ when finite, and the branching extinction probability. A binomial branching process and a Poisson branching process have different offspring distributions even when their means agree.

Let $q\in (0,1]$ be the branching extinction probability of a Galton-Watson process with offspring probability generating function $f$. Conditional on extinction, the probability of $j$ children is multiplied by $q^j/q$: every child's descendants must also become extinct. Hence the new probability generating function is $f_q$ and its mean is $f^{\prime }(q)$. If $f^{\prime }(q)<1$, the total progeny of a branching process has conditional expected value $1/(1-f^{\prime }(q))$, and unconditionally $\mathbb{E}[T;T<\infty ]=q/(1-f^{\prime }(q))$. The Markov inequality gives a finite-total-progeny tail bound without discarding the survival mass.

A Galton-Watson process with a Poisson distribution of offspring of mean $\mu$ has this probability generating function. For $\mu =1+\epsilon >1$ its branching survival probability $r$ satisfies $-\log (1-r)=(1+\epsilon )r$, and $2\epsilon /(1+2\epsilon )\le r\le 2\epsilon$. Indeed $\epsilon ={\sum }_{j\ge 1}{r}^j/(j+1)$ lies between $r/2$ and $r/[2(1-r)]$. These exact inequalities belong to the Poisson branching process, not to every finite binomial branching process.

A Galton-Watson process whose offspring law is a binomial distribution $\mathrm{Bin}(n,p)$ has mean $np$ and the displayed offspring probability generating function. Its branching extinction probability is the smallest root of $q=f(q)$ in $[0,1]$. It dominates a breadth-first exploration of a binomial random graph by allowing each explored vertex up to $n$ independent possible children, including previously exposed or already discovered vertices as phantom children.

For $p=(1+\epsilon )/n$, the branching survival probability satisfies $1-\rho =(1-p\rho {)}^n$. If $(1+\epsilon {)}^2<n$, comparison with a Poisson branching process and expansion of the logarithm giveFor the upper bound use $\epsilon ={\sum }_{j\ge 1}(1-n{p}^{j+1}){\rho }^j/(j+1)$ and retain its first nonnegative term. For fixed $n>1$, the leading term is instead $2n\epsilon /(n-1)$. In particular $n=2$ gives $\rho =4\epsilon /(1+\epsilon {)}^2$, showing that the uncorrected exact bound $\rho \le 2\epsilon$ is false for small positive $\epsilon$.

For $0<\epsilon \le 1/4$ and $n\epsilon \ge 2$, the uncorrected exact upper bound does hold for the binomial branching process. Here $n{p}^2\le \epsilon$ and $n{p}^3\le 1/4$, so at $x=2\epsilon$ the first two terms of the nonnegative series give $\epsilon (1-n{p}^2)+(4/3){\epsilon }^2(1-n{p}^3)\ge \epsilon$. Monotonicity of that series yields $\rho \le 2\epsilon$. This recovers the intended large-$n$ bracket without claiming it for every finite reproduction law.

The total progeny counts all individuals, including the initial ancestor, in a Galton-Watson process. It is infinite on survival. If the offspring mean is $m<1$, the expected generation size in a Galton-Watson process and the monotone convergence theorem give $\mathbb{E}T=1/(1-m)$.

The offspring probabilities $P(K=j)=2^{-j-1}$ for $j\ge 0$ have expected value one. For one initial individual, the branching-process generating-function iteration givesFor $n\ge 1$ the PGF disk is $|s|<1+1/n$; $G_0(s)=s$ separately. Conditional on survival, the population is positive geometric with success probability $1/(n+1)$, leading to the exponential limit of surviving geometric branching.

For the stated critical geometric offspring law, the conditional upper tail is exactly $[n/(n+1){]}^{\lfloor nx\rfloor }$ for $x\ge 0$. Its logarithm tends to $-x$, proving an exponential distribution limit of rate one without a transform continuity theorem. The unconditional mass at zero tends to one, so survival conditioning changes the relevant limiting population scale.

Conditioning on the initial individual's children gives independent copies of the population $n$ generations later. Their PGFs multiply, and averaging the product over the offspring number yields $G(G_n(s))$. Conditioning on the last generation gives $G_n(G(s))$ as well; both agree because $G_n$ is the $n$fold iterate of $G$.

With one initial ancestor and independent offspring counts of finite mean and variance, conditioning on the current generation gives the displayed recurrences. For $\mu \ne 1$ the variance is ${\sigma }^2{\mu }^{n-1}({\mu }^n-1)/(\mu -1)$ for positive generation index. At $\mu =1$ it is $n{\sigma }^2$. At zero offspring mean the distribution is concentrated at zero and later generations vanish. These formulas are for the Galton-Watson process, not arbitrary dependent reproduction.

If $G$ is the offspring probability-generating function, the eventual extinction probability is the smallest fixed point of $G$ in $[0,1]$.

For a Galton-Watson process with one ancestor this is the probability that some generation is empty. It is the smallest fixed point of the offspring probability generating function in $[0,1]$; the complementary survival probability is $1-q$. A branching process conditioned on extinction reweights reproduction using this fixed point.

For a Galton-Watson process started from one ancestor, this is the probability that every generation is nonempty. It is the complement of the branching extinction probability. The binomial branching survival correction distinguishes finite-binomial reproduction from the Poisson branching process near mean one.

If a Galton-Watson process starts from one individual and has offspring mean $m$, conditioning on generation $n$ gives $\mathbb{E}[Z_{n+1}\mid Z_n]=m{Z}_n$. Induction therefore gives $\mathbb{E}[Z_n]=m^n$.

For offspring mean $\mu >1$ and variance ${\sigma }^2$, Taylor expansion at one givesfor the extinction probability $d$.