Galton-Watson process ($Z_{n+1}={\sum }_{j=1}^{Z_n}{\xi }_{n,j}$)

A Galton-Watson process is a branching process that counts individuals by generation. Start with one ancestor, $Z_0=1$, and let all offspring counts ${\xi }_{n,j}$ be independent and identically distributed random variables taking nonnegative integer values with a common offspring distribution. ThenThe empty sum is zero: zero is an absorbing state, so once a generation is empty every later generation is empty. The same offspring distribution applies to every individual in every generation. ^[ref]

For a concrete offspring distribution, take $p_0=1/4$, $p_1=1/4$, $p_2=1/2$, and $p_k=0$ for $k\ge 3$. An individual has no children with probability $1/4$, one with probability $1/4$, and two with probability $1/2$. The offspring expected value is $\mu =5/4$. A possible sequence of generation sizes is $1,2,1,0,0,\dots$: two children need not lead to a permanently growing family.

The probability generating function $F(s)=1/4+s/4+s^2/2$ gives the exact generation probability distributions through branching-process generating-function iteration. With $G_0(s)=s$ and $G_{n+1}(s)=F(G_n(s))$, the second generation hasThus $\mathbb{P}(Z_2=0)=11/32$ and $\mathbb{E}[Z_2]=25/16$. The figure shows full generation probability mass functions, computed by polynomial function composition, through generation six; no simulated frequencies are used.

The contrast is striking: the expected generation size in a Galton-Watson process grows as $(5/4{)}^n$, while the branching extinction probability is $1/2$. By generation six, $\mathbb{P}(Z_6=0)\approx 0.462186$ although $\mathbb{E}[Z_6]\approx 3.814697$. Larger surviving families carry the rising expected value; that mean is an average over possible families, not a forecast of one family's path. The Galton-Watson extinction fixed point turns an unbounded number of future generations into a single equation for this probability.

The historical question was the disappearance of surnames passed through male descendants. In Watson and Galton, On the Probability of the Extinction of Families, pages 139–140, Francis Galton formulates a constant-law model counting sons who reach adulthood, and Watson computes later generation probability distributions by composing generating functions. Those are assumptions of their model, rather than a claim that actual human reproduction follows this offspring distribution.

The offspring probability distribution of a Galton-Watson process is the law of one individual's number of children: $p_k=\mathbb{P}(\xi =k)$ for $k\ge 0$, with $p_k\ge 0$ and ${\sum }_{k\ge 0}{p}_k=1$. Its probability generating function and, when finite, its expected value areUse $0^0=1$ when evaluating the probability generating function at zero: $F(0)=p_0$ and $F(1)=1$.

For $p_0=p_1=1/4$ and $p_2=1/2$, $F(s)=1/4+s/4+s^2/2$, $\mu =5/4$, and the offspring variance is $11/16$: $\mathbb{E}[{\xi }^2]=9/4$ and $\mathrm{Var}(\xi )=9/4-(5/4{)}^2$. The generation probability mass functions pictured under Galton-Watson process come from repeatedly composing this probability generating function. They describe the whole generation, whereas $(p_k)$ describes one individual's reproduction. ^[ref]

The whole offspring distribution matters for extinction. Another law, $p_0=3/8$ and $p_2=5/8$, has the same offspring mean $5/4$ but branching extinction probability $3/5$, since $3/8+5s^2/8=s$ has roots of a polynomial $3/5$ and $1$. Consequently the two laws have the same expected generation size in a Galton-Watson process at each generation but different survival chances. A binomial branching process and a Poisson branching process likewise specify different offspring distributions; a common mean does not make their probability generating functions identical.

For $0<\alpha ,\beta <1$, this probability generating function has probabilities $p_0=1-\alpha$ and $p_k=\alpha \beta (1-\beta )\cdots (k-1-\beta )/k!$ for $k\ge 1$, where the product after $\beta$ is empty for $k=1$. All probabilities are positive and sum to one, while the expected value is infinite. In a Galton-Watson process starting with one individual, the generation-$n$ probability generating function is $G_n(s)=1-{\alpha }^{(1-{\beta }^n)/(1-\beta )}(1-s{)}^{{\beta }^n}$. The branching extinction probability is $1-{\alpha }^{1/(1-\beta )}$, obtained by taking the limit of $G_n(0)$ and using that extinction by generation $n$ is an increasing sequence of events.

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.

For offspring $\mathrm{Bin}(k,p)$ with $0<p<1$ and $kp>1$, let $\eta \in (0,1)$ be the branching extinction probability. Conditioning on extinction changes the offspring law to $\mathrm{Bin}(k,\tilde{p})$ with the displayed parameter. Indeed, the probability of $j$ children is multiplied by ${\eta }^{j-1}$, so the new probability generating function is $f(\eta s)/\eta$. Since $f(s)=(1-p+ps{)}^k$ and $f(\eta )=\eta$, this equals $((1-p+p\eta s)/(1-p+p\eta ){)}^k$. Its mean is $k\tilde{p}=f^{\prime }(\eta )<1$, because strict convexity of $f(s)-s$ and its zeros at $\eta$ and one force a negative derivative at the smaller zero. The conditioned process therefore has an exponentially decaying total-progeny tail. Unconditionally that tail instead converges to the survival mass $1-\eta$, with an exponentially small correction. When extinction has probability zero, conditioning on it does not define this law.

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.

Start with $Y_0\sim \mathrm{Poisson}(\theta )$ and conditionally let $Y_i\sim \mathrm{Poisson}(\theta Y_{i-1})$. The mean generation size is ${\theta }^{i+1}$. The log-likelihood is $S_n\log \theta -\theta T_n$ plus a parameter-free term, where $S_n={\sum }_{i=0}^n{Y}_i$ and $T_n=1+{\sum }_{i=0}^{n-1}{Y}_i$. Expected negative curvature gives the displayed Fisher information, bounded as the horizon grows. Extinction makes the observations eventually all zero, so one longer observed family does not supply indefinitely increasing information.

// Target: convergence-of-random-variables.bigb

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)$.

For a branching process starting from one individual with offspring two with probability $p$ and zero otherwise, the finite total progeny is odd. Exploring individuals gives an active queue beginning at one, with increments $+1$ or $-1$. A first hit of zero at time $2j+1$ requires $j$ positive and $j+1$ negative increments and no earlier empty queue. The Catalan number $C_j=\left(\genfrac{}{}{0ex}{}{2j}{j}\right)/(j+1)$ counts these admissible sequences, for example by the reflection principle after removing the final down step. Independence then gives the displayed mass formula.

If $p\ne 1/2$, $b=4p(1-p)<1$ and $C_j\le 4^j$, so $\mathbb{P}(K=2j+1)\le (1-p)b^j$. Choosing $c=\min \{-\log (1-p),-\frac{1}{2}\log b\}>0$ bounds every finite mass by $e^{-c(2j+1)}$. This does not exclude an atom at infinity. In the supercritical case that atom has mass $(2p-1)/p$. At criticality $p=1/2$, the process dies out almost surely, but the Catalan number asymptotic gives masses proportional to $j^{-3/2}$ and hence infinite mean total progeny.

If a Galton-Watson process starts from one ancestor and has bounded nonnegative integer offspring $Z$ with $\mathbb{E}Z<1$, its total progeny $T$ obeys $\mathbb{P}(T>n)\le e^{-cn}$ for some $c>0$ and all integers $n\ge 1$. Explore one individual at a time. The unexplored queue has size $1+{\sum }_{j=1}^t(Z_j-1)$ until its first hit of zero, whose hitting time is $T$. Hence $T>n$ implies ${\sum }_{j=1}^n(Z_j-1)\ge 0$. Boundedness makes $M(\theta )=\mathbb{E}{e}^{\theta (Z-1)}$ finite near zero, with $M(0)=1$ and $M^{\prime }(0)=\mathbb{E}Z-1<0$. Choose $\theta >0$ with $M(\theta )<1$. The exponential Markov inequality gives the desired bound with $c=-\log M(\theta )$. The same proof works whenever the offspring law has an exponential moment near zero, even without boundedness.

For an almost surely finite total progeny of a branching process, let $F$ be the offspring probability generating function and $g$ that of the total, including one ancestor. Conditional on $k$ children, the total is one plus the sum of $k$ independent descendant totals. Independence and the law of total expectation give $g(s)=sF(g(s))$ for $|s|\le 1$, including the empty-product case $k=0$. If the offspring expected value is $m=F^{\prime }(1-)<1$, differentiation for $0<s<1$ gives $g^{\prime }(s)=F(g(s))/(1-s{F}^{\prime }(g(s)))$. The denominator is positive because $F^{\prime }(g(s))\le m$. Letting $s\uparrow 1$ and using the monotone convergence theorem on the derivative series proves $\mathbb{E}T=1/(1-m)$, establishing finiteness rather than assuming it. For Poisson branching process offspring, $F(z)=e^{m(z-1)}$.

Consider a Galton-Watson process started by one individual, with offspring count $2$ with probability $p<1/2$ and $0$ with probability $q=1-p$. Let $N$ count individuals producing two offspring. At the first generation, either $N=0$, or $N=1+N_1+N_2$ for independent copies $N_1,N_2$. Its probability generating function therefore satisfies $G=q+ps{G}^2$ andThe branch is fixed by $G(0)=q$. Differentiation at $s=1$ gives $\mathbb{E}[N]=p/(1-2p)$. Alternatively, generation $t$ has expected size $(2p{)}^t$, so its expected splitting count is $p(2p{)}^t$ and summing gives the same result. The total progeny is $2N+1$, since every split creates two new individuals.

Count the ancestor and the next $n-1$ generations of a Galton-Watson process. Conditioning on the ancestor's offspring, their independent descendant trees each have the preceding finite-horizon probability generating function, proving the displayed recursion. If the count instead excludes the ancestor, the recursion is ${\hat{H}}_{n+1}(s)=G(s{\hat{H}}_n(s))$ with ${\hat{H}}_0=1$. The indexing convention must be specified.

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.

Start a branching process with one ancestor and offspring distribution $\mathbb{P}(N=k)=2^{-k-1}$ for $k\ge 0$. Its probability generating function is $G_N(s)=1/(2-s)$ and its mean offspring count is $1$, making it a critical branching process. Splitting the family at the ancestor gives the total progeny recursion $Z=1+{\sum }_{i=1}^N{Z}_i$. The probability generating function of an independent random sum then gives $G_Z=s/(2-G_Z)$, whose root satisfying $G_Z(0)=0$ is $1-\sqrt{1-s}$. Its limit at $s\uparrow 1$ equals $1$, consistent with finite total progeny almost surely; its derivative diverges there, so the expectation of $Z$ is nevertheless infinite.

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.

For a Galton-Watson process with one ancestor and offspring probability generating function $F$, the branching extinction probability $q$ is the smallest fixed point of $F$ in $[0,1]$. A direct way to find it is to compute extinction by generation $n$:Zero is an absorbing state, so extinction by generation $n$ is exactly the event $Z_n=0$. ^[ref]

For $F(s)=1/4+s/4+s^2/2$, the equation isBoth $1/2$ and $1$ are fixed points, but iteration from zero selects $q=1/2$. The first values are $q_1=1/4$, $q_2=11/32$, $q_3=809/2048\approx 0.395020$, and $q_6\approx 0.462186$. Iteration started at $1$ would stay at $1$ forever and would give the wrong extinction answer for this offspring distribution.

The vertical steps in the figure apply the offspring probability generating function; horizontal steps return to the diagonal to start the next iteration. This gives a useful numerical calculation even when solving $F(s)=s$ explicitly is difficult. For the displayed law, every finite iteration is a lower bound for the eventual branching extinction probability; at generation six, about $0.037814$ additional extinction probability remains beyond the current empty families.

Why the smallest fixed point? The ancestor's children's descendant families are independent; given $k$ children, all are empty $n$ generations later with probability $q_n^k$. Averaging gives $q_{n+1}={\sum }_k{p}_k{q}_n^k=F(q_n)$. The increasing extinction events give the limit $q$, and continuity of the probability generating function yields $F(q)=q$. For any other fixed point $r\in [0,1]$, $q_0\le r$ and monotonicity of $F$ imply $q_n\le r$ at every step; hence $q\le r$. ^[ref]

For a Galton-Watson process, replacing an individual's reproduction by a one-descendant uneventful step with probability $q<1$ changes its offspring probability generating function to the displayed mixture. Its fixed-point equation reduces to $G(z)=z$, so the smallest fixed point and hence the extinction probability of a branching process are unchanged. The mean is $q+(1-q)G^{\prime }(1)$, which also preserves the subcritical/critical/supercritical classification. The excluded case $q=1$ never reproduces or dies and need not share the extinction probability.

For a Galton-Watson process with one ancestor, the branching extinction probability is the probability that some generation is empty:The equality uses the absorbing state at zero. The complementary branching survival probability $1-q$ is the probability that every generation is nonempty. The Galton-Watson extinction fixed point computes $q$ from the offspring distribution.

For $p_0=p_1=1/4$, $p_2=1/2$, one ancestor has $q=1/2$. Starting instead from $m$ ancestors with independent descendant families givesAll $m$ families must die out. With three ancestors, eventual extinction has probability $1/8$ and survival has probability $7/8$; by generation two, extinction has probability $(11/32{)}^3=1331/32768\approx 0.040619$. Extra ancestors change the extinction probability without changing the offspring distribution. ^[ref]

For finite offspring mean $\mu$, the extinction classification is:

The critical exception is $p_1=1$: every individual has exactly one child, $F(s)=s$, and $Z_n=1$ forever from one ancestor. Thus $\mu =1$ but $q=0$; a blanket claim that every critical Galton-Watson process becomes extinct would be false. These cases concern the Galton-Watson process with its common offspring distribution and independence assumptions. ^[ref]

This probability answers whether any lineage persists, which the offspring mean alone cannot quantify in the supercritical case. A branching process conditioned on extinction uses the same fixed point to reweight reproduction and describe families known eventually to die out.

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.

For a Galton-Watson process starting with one ancestor and finite offspring mean $\mu$, the expected value of the generation size is $\mathbb{E}[Z_n]={\mu }^n$. At $n=0$ it is one, including when $\mu =0$; zero offspring mean forces every later generation to be empty. With $m$ initial ancestors, the expected value is $m{\mu }^n$.

For $p_0=p_1=1/4$, $p_2=1/2$, the offspring mean is $5/4$. The exact calculations used in the generation probability mass function figure under Galton-Watson process give:

Nearly half the families are already empty at generation six, yet the expected value exceeds three. Since empty families contribute zero,whenever $q_n<1$. At generation six this conditional expectation is about $7.092969$. Conditioning on being nonempty now differs from conditioning on eventual survival: some presently nonempty families will still die out. The eventual branching extinction probability is $1/2$, even as the unconditional expected value grows without bound.

The expected value is useful for computing average population counts and, in the subcritical case, the expected value of the total progeny of a branching process. Its simple formula comes from one local calculation: linearity of expectation and the independent and identically distributed offspring counts giveThe tower property of conditional expectation gives the second equality; starting from $\mathbb{E}[Z_0]=1$ gives the formula. It describes an average over the generation probability distribution, not deterministic growth of an individual family. ^[ref]

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