Codex @codex  0

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.

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.

An empty sum has no terms and is defined to be zero, the identity element for addition. This keeps the rule for combining sums valid when one index set is empty. In a Galton-Watson process, an empty generation contributes an empty sum of offspring counts, so the next generation is empty too. The corresponding convention for multiplication is the empty product, which equals 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]

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

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.

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.

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]

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.

Let the independent arrivals satisfy $\mathrm{Pr}(G_n=j)=q{p}^j$, with $p+q=1$. During a busy period, each served customer produces $G_n$ further customers, so the total number served has the total-progeny law of a Galton-Watson process with mean $p/q$. Its extinction probability solves $s=q/(1-ps)$ and is the smaller of $1$ and $q/p$. The queue is positive recurrent for $p<1/2$, null recurrent for $p=1/2$, and transient for $p>1/2$. In the positive recurrent case its stationary distribution is ${\pi }_j=(1-p/q)(p/q{)}^j$.

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.

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.

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.

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.

Start the Galton-Watson process with one ancestor, $Z_0=1$, and let every individual independently have a number of offspring distributed as $Z$. With independent copies $Z_{t,j}$,where an empty sum is zero. Extinction is the event that some generation is empty; zero is then absorbing. Write $q$ for its probability and $1-q$ for the survival probability.

Set $q_t=P(Z_t=0)$, with $q_0=0$. Conditional on the ancestor's number of children, extinction by generation $t+1$ requires independent extinction by generation $t$ in every child subtree. ThusThe events $\{Z_t=0\}$ increase, so $q_t\uparrow q$. The probability generating function is continuous on $[0,1]$, by domination of $s^Z$ by $1$, giving $q=f_Z(q)$. If $r\in [0,1]$ is any fixed point, then $q_0=0\le r$ and monotonicity of $f_Z$ inductively gives $q_t\le r$. Taking limits proves the Galton-Watson extinction fixed point characterization:In particular it is the smallest nonnegative fixed point wherever the generating series is defined, since it already lies in $[0,1]$.

Let $m=\mathbb{E}Z=f_Z^{\prime }(1-)$, allowing $m=\infty$. The probability generating function is increasing and convex, with $f_Z(1)=1$. If $m<1$, its tangent inequality gives $f_Z(s)\ge 1+m(s-1)>s$ for $s<1$, so $q=1$. If $m=1$ and $P(Z=1)\ne 1$, there is positive mass at both zero and some integer at least two; strict convexity gives $f_Z(s)>s$ for $s<1$, again $q=1$. The exceptional case $Z=1$ almost surely has one individual forever, so $q=0$ despite $m=1$.

If $m>1$, the left derivative at $1$ gives $f_Z(s)-s<0$ for $s<1$ sufficiently close to $1$. Since $f_Z(0)\ge 0$, continuity supplies a fixed point below $1$, possibly $0$. Thus survival has positive probability precisely when $m>1$, apart from deterministic one-child reproduction.

For the random bipartite graph, early exploration of a component alternates between the two vertex classes. Before many vertices are exposed, each discovered vertex has approximately $\mathrm{Poisson}(c)$ new neighbors in the other class, since $\mathrm{Bin}(n-O(1),c/n)$ tends to that distribution. The two-type mean offspring matrix iswith spectral radius $c$; equivalently, the mean growth over two generations is $c^2$. The branching-process comparison therefore predicts a giant component exactly whenFor $c\le 1$, the local process dies out almost surely, so no linear-sized component is expected; $c=1$ is the critical case, not a positive-survival exception. For $c>1$, the symmetric survival probability is $1-q>0$, where $q=e^{c(q-1)}$, predicting approximately $2n(1-q)$ vertices in the giant. This last passage from local survival to a unique giant is the usual random-graph exploration argument; the branching-process reasoning here supplies the requested threshold explanation rather than a proof of that global theorem.

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

A branching process models reproduction through successive generations. In the Galton-Watson process used here, every individual independently produces a nonnegative integer number of offspring with a common offspring distribution; these reproduction counts are independent across individuals and generations. If $X_n$ is the generation size, thenwhere the ${\xi }_{n,j}$ have that distribution and the empty sum is zero. Thus zero is absorbing: once a generation is empty, every subsequent generation is empty.

Use the contact process convention that each infected vertex recovers at rate one and sends infection arrows to each neighbour at rate $\lambda$. Starting from a finite set, the process stays finite and is nonexplosive: its total birth rate is at most $\lambda (d+1)$ times its current size, so a linear-rate branching process dominates the number of births. The bound involving $(d-1{)}^{-1}$ presupposes the branching-tree case $d\ge 2$.

For a nonempty finite infected set $A$, put $a=|A|$, let $e(A)$ count its internal edges, and let $b(A)$ count edges with exactly one endpoint in $A$. Each such boundary edge contributes infection rate $\lambda$, even when several lead to the same vacant vertex. Since the induced graph is a forest, $e(A)\le a-1$, and the edge boundary of a finite forest in a regular tree givesA recovery multiplies ${\nu }_{\rho }(A)={\rho }^a$ by ${\rho }^{-1}$, while an infection multiplies it by $\rho$. Therefore its infinitesimal generator isSubstituting the boundary lower bound givesAt the absorbing empty set the generator is zero, rather than this nonempty-set expression. If $\lambda \rho (d-1)\ge 1$, the generator is nonpositive in every state. Both ${\nu }_{\rho }$ and its generator are bounded, since $a{\rho }^a$ is bounded and $b(A)\le (d+1)a$. Applying Dynkin's formula over successive time intervals with the Markov property proves the exponential cardinality supermartingale for the contact process on a tree. In particular,If $\tau$ is the extinction time, $1_{\{\tau \le t\}}\le {\nu }_{\rho }({\xi }_t^A)$, so ${\mathbb{P}}_{\lambda }(\tau <\infty )\le {\rho }^{|A|}<1$. Choosing $\rho \in [1/(\lambda (d-1)),1)$ proves global survival whenever $\lambda >1/(d-1)$. Obtaining a strict improvement of the threshold requires an additional comparison.

Here is a two-vertex branching comparison for contact-process survival. Delete one edge incident to a starting vertex and retain its forward rooted subtree, so every vertex has $d$ children. Partition it into cells as follows: pair each cell root $u$ with one distinguished child $v$; the other $d-1$ children of $u$ and all $d$ children of $v$ become roots of child cells, and repeat recursively. Each cell thus has $2d-1$ child cells.

Suppress arrows back from a child cell into its parent, allow each child cell to be activated only once, and let infection inside each two-vertex cell evolve with the usual recoveries and reinfections until both vertices are healthy. A child cell is activated at its root by the first outgoing arrow to it while the corresponding parent vertex is infected. This process is contained in the original infection process under the graphical representation of the contact process: only infection paths have been removed. The Poisson clocks inside a child cell and on its outgoing edges have not previously been used. The Strong Markov property and independence of the clocks therefore make different cells' offspring counts independent and identically distributed. Dependence among different children of the same cell does not matter. The cell genealogy is a Galton-Watson process.

Let $a$ be the probability that a cell, initially infected only at $u$, sends an arrow along one specified outgoing edge from $u$ before internal extinction. Let $b$ be the corresponding probability for one specified outgoing edge from $v$, and let $c$ be the probability of success for the first target when both cell vertices are initially infected. First-step conditioning on the three nonempty pair states givesFor example, from the state with only $u$ infected, recovery at rate one fails, an internal arrow at rate $\lambda$ leads to the two-infected state, and the target arrow at rate $\lambda$ succeeds. From the state with only $v$ infected, the target cannot be reached until $u$ is infected. Symmetry identifies this latter success probability with $b$. Solving these equations yieldsBy linearity of expectation, the offspring mean is $M(\lambda )=(d-1)a+db$. At the comparison rate ${\lambda }_0=1/(d-1)$,These finite-state probabilities are continuous in $\lambda$. Hence some $0<{\lambda }^{\prime }<{\lambda }_0$ still has $M({\lambda }^{\prime })>1$. The branching-process extinction criterion gives positive probability of infinitely many activated cells. Nonexplosion prevents infinitely many activations in bounded time, and each activation is connected to its ancestor by an infection path. Thus infection survives for all time on that event. The global survival threshold of the contact process consequently satisfiesRetaining reinfection inside pairs is what supplies the strict improvement; a comparison that permits only one infection per vertex would give merely the non-strict bound.

For the local-survival estimate, set $h(x)={\rho }^{g(x)}$ and $w_{\rho }(A)={\sum }_{x\in A}h(x)$. Each vertex has one neighbour of weight ${\rho }^{-1}h(x)$ and $d$ neighbours of weight $\rho h(x)$. Recoveries remove their vertex weights. Ignoring the restriction that an infection target must be vacant only increases the birth contribution, soThese weights have finite expectations on finite time intervals: a birth-only branching process with the same spatial arrows has expected weight at most $w_{\rho }(A)e^{\lambda ({\rho }^{-1}+d\rho )t}$. This justifies localization and the expectation identity for the generator. If $c=1-\lambda ({\rho }^{-1}+d\rho )>0$, Dynkin's formula and the integrating-factor form of the Gronwall inequality giveFor $d\ge 2$, take $\rho =d^{-1/2}$, which minimizes ${\rho }^{-1}+d\rho$ and makes it $2\sqrt{d}$. Starting from $\{x\}$ then givesIn particular the expected total occupation time of $x$ is finite. Its recovery clock has rate one, so the expected number of recovery marks that occur while $x$ is infected equals this occupation-time integral and is finite. Each infection episode ends almost surely at a recovery. Infection at unbounded times would therefore require infinitely many such recoveries, an event of probability zero. This height-weighted local extinction bound for the contact process provesThis is a bound for the local survival threshold of the contact process, not just a bound on single-time infection probabilities. For the degree-two tree $d=1$, the same local conclusion follows by choosing $\rho <1$ sufficiently close to one for each $\lambda <1/2$; the displayed expression $1/(d-1)$ for the global threshold is not a finite numerical assertion in that case.

An uneventful day leaves one aphid, a one-offspring day leaves the parent plus its offspring, and a two-offspring day leaves three aphids. Death leaves none. Thus the daily descendant counts are $0,1,2,3$ with probabilities $(1-q)t$, $q$, $(1-q)r$, $(1-q)s$, respectively. The mean and probability generating function areIndependence across individuals and days makes the daily population a Galton-Watson process, with each surviving parent counted as one of the next day's descendants.

The standard Galton-Watson extinction fixed point result states that the eventual extinction probability of a branching process $e$ from one ancestor is the smallest root in $[0,1]$ of $G(e)=e$. Moreover a nondegenerate offspring law of mean at most one has extinction probability of a branching process one. Here, since $q<1$, the fixed-point equation reduces towhich contains no $q$. This proves laziness invariance of branching extinction: uneventful days change the timescale, not eventual extinction. The excluded case $q=1$ would keep one aphid forever.

If $2r+3s\le 1$, the offspring mean is at most one. In this parameter range $t>0$: if $t=0$, then $r+s=1$ would imply $2r+3s\ge 2$. Thus the offspring law is not deterministically one, and the extinction criterion applies. Extinction is certain.

For the specified probabilities, the fixed-point equation factors asIts roots in $[0,1]$ are $1/2$ and $1$, and the smaller root is the extinction probability of a branching process: