Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2011 / B / 6

A Galton-Watson process starts with one ancestor, $X_0=1$. Given generation size $X_r$, definewhere all offspring variables are independent with common distribution $Z$. The empty sum is zero, so zero is absorbing. Its extinction probability isFor the probability generating function $f(s)=\mathbb{E}[s^Z]$, the allowed fixed-point characterization isFor binomial offspring, $f(s)=(1-p+ps{)}^k$, with $f(1)=1$, $f^{\prime }(1)=kp$, and $f$ convex on $[0,1]$.

First assume $0<p<1$. If $k=0$, extinction occurs immediately. For $k=1$, $f(s)-s=(1-p)(1-s)>0$ for $s<1$, so the only fixed point is one. For $k\ge 2$, strict convexity givesIf $kp\le 1$, the right-hand side is at least $s$, so no fixed point below one exists and $\eta =1$. If $kp>1$, $f(s)-s<0$ for $s$ just below one, whereas $f(0)>0$. Continuity supplies a fixed point in $(0,1)$; hence $\eta <1$. Thus in the nondegenerate parameter range,For completeness, if binomial endpoint parameters are allowed, $p=0$ or $k=0$ gives $\eta =1$, while $p=1$ and $k\ge 1$ gives deterministic positive offspring and $\eta =0$. In particular $(k,p)=(1,1)$ survives forever despite mean one. Over $k\in \{0,1,\dots \}$ and $p\in [0,1]$, the full condition is

Explore the family tree one individual at a time, maintaining a queue of individuals not yet explored. Initially its size is $Y_0=1$. Exploring individual $t$ removes it and adds its independent offspring $Z_t$, so before the queue empties,One may define the independent increments indefinitely, but the tree exploration stops at $T=\inf \{t:Y_t=0\}$. This hitting time is the total progeny, including the ancestor. Since each increment is at least $-1$, a queue cannot jump below zero before hitting zero. If it never hits zero, the family has infinitely many individuals.

Suppose $kp<1$. A Chernoff bound in moment-generating-function form says that for independent $W_j$ and $\theta >0$,Here take $W_j=Z_j-1$, withWe have $M(0)=1$ and $M^{\prime }(0)=kp-1<0$, so some $\theta >0$ has $M(\theta )<1$. Let $c=-\log M(\theta )>0$. If $T>n$, the queue is still positive after $n$ explorations; its integer value is at least one, giving ${\sum }_{j=1}^n(Z_j-1)\ge 0$. ThereforeThis proves the claimed bound without appealing to a general branching-process tail theorem.

The argument proves the more general exponential total progeny tail for bounded subcritical offspring.

First take $0<p<1$ and $kp>1$. Part (a) gives an extinction probability $\eta \in (0,1)$. Write $p_j=\mathbb{P}(Z=j)$. Conditional on the ancestor having $j$ children, extinction requires extinction of all $j$ independent descendant trees and has probability ${\eta }^j$. Bayes' rule therefore gives the conditional offspring lawIts sum is $f(\eta )/\eta =1$. Conditional on extinction of all descendant trees, those trees remain independent, each with its own extinction-conditioned law. Thus the entire conditioned process is a Galton–Watson process with offspring generating functionFor binomial offspring, using $\eta =(1-p+p\eta {)}^k$ givesIts mean is $k\tilde{p}=f^{\prime }(\eta )<1$. Indeed, $f(s)-s$ is strictly convex and has its two zeros at $\eta$ and one, so its derivative at the first zero is strictly negative. This proves subcriticality directly from the generating function.

Let $T$ be total progeny, taking value infinity on survival. Apply part (b) to the conditioned process. For some $c>0$,Thus the unconditional tail tends to the positive survival probability $1-\eta$, with an exponentially small finite-extinction contribution. It does not decay to zero.

If $p=1$ and $kp>1$, extinction has probability zero and conditioning on it does not specify a probability law. In that deterministic case total progeny is infinite and $\mathbb{P}(T>n)=1$ for every finite $n$.

The nondegenerate law above is the binomial branching process conditioned on extinction.