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.

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

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.

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.

For a Galton-Watson process, condition on the number $K$ of children of the initial individual. The descendants of these children over the next $n$ generations are independent copies of $X_n$. The probability generating function of their total, conditional on $K=k$, is $G_n(s{)}^k$. Averaging over the family-size law givesThis is the branching-process generating-function iteration. Conditioning instead on the last generation gives $G_n(G(s))$; both orders agree because $G_n$ is the $n$th iterate of the same function $G$. The argument holds on the usual PGF domain $|s|\le 1$, with larger domains available when the corresponding expectations converge.

The function $x{e}^{-x}$ is strictly increasing on $(0,1)$ and strictly decreasing on $(1,\infty )$. Hence for each $\lambda >1$ there is a unique $\theta ={\lambda }^{\ast }\in (0,1)$ with $\theta e^{-\theta }=\lambda e^{-\lambda }$.

Apply the subcritical component estimates to $G(n,\theta /n)$. For a specified vertex, the exact tree-component expectation in the Erdős-Rényi model gives the limiting probability that it lies in a tree component of order $j$:For each fixed $j$, the probability of a non-tree graph component of that size is $O_j(1/n)$: a spanning tree and one extra edge are necessary. Moreover the Galton-Watson process exploration estimate from the preceding proof bounds the probability of order greater than $K$ by $e^{-{\delta }_{\theta }(K-1)}$, uniformly in $n$, where ${\delta }_{\theta }=\theta -1-\log \theta >0$. First let $n\to \infty$ for fixed $K$, then let $K\to \infty$. No probability mass escapes to large components or non-tree components, so ${\sum }_{j\ge 1}{a}_j=1$. Multiplying by $\theta$ and using its defining identity givesEquivalently, the rooted-tree generating function selects the smaller solution of $T{e}^{-T}=\lambda e^{-\lambda }$. The choice of that branch is essential; the larger solution $\lambda$ is not the value of this convergent series.

Assume $0<\lambda =1-\epsilon <1$, as required for this nontrivial subcritical binomial random graph. Put $\delta =\lambda -1-\log \lambda >0$. A breadth-first exploration of a binomial random graph is dominated by a Galton-Watson process whose offspring counts are independent random variables with law $\mathrm{Bin}(n,\lambda /n)$. If its total progeny $T$ is at least $j$, the first $j-1$ offspring counts sum to at least $j-1$. Their moment-generating function is bounded by that of a Poisson distribution of mean $\lambda (j-1)$. The exponential Markov inequality, optimized at $t=-\log \lambda$, yieldsTaking $j=\lceil (1+\eta )\log n/\delta \rceil$ for any fixed $\eta >0$, a union bound over all starting vertices gives $\mathbb{P}(L_1\ge j)=o(1)$.

For the matching lower bound, let $X_j$ count tree components of order $j$. The tree-component expectation in the Erdős-Rényi model is exactlyFor $j=O(\log n)$, the Stirling formula givesChoose $j=\lfloor (1-\eta )\log n/\delta \rfloor$, with $0<\eta <1$. Then $\mathbb{E}{X}_j\to \infty$. Distinct overlapping vertex sets cannot both be graph components. For disjoint sets, the joint probability differs from the product only because the $j^2$ between-set edges were counted twice as absent. ThusIt follows that $\mathrm{var}{X}_j/(\mathbb{E}{X}_j{)}^2=o(1)$. The second moment method gives $X_j>0$ with high probability. Combining both bounds, and then taking arbitrarily small fixed $\eta$, proves the sharp subcritical largest-component scaleFinally the Taylor expansion of $-\log (1-\epsilon )$ gives $\delta ={\epsilon }^2/2+{\epsilon }^3/3+\cdots$. The endpoint $\lambda =0$ has no edges and is excluded from this logarithmic asymptotic.

For the probability generating function $G(t)=\mathbb{E}[t^X]$, differentiation givesThe second derivative is a factorial moment, not the raw second moment.

In the Galton-Watson process, condition on $X_n=m$. The next generation is a sum of $m$ independent offspring counts, and so its conditional generating function is $G(t{)}^m$. Averaging over $X_n$ givesThe conditional mean is $m\mu$ and the conditional variance is $m{\sigma }^2$. Thus iterated expectation gives $\mathbb{E}[X_n]={\mu }^n$ from one ancestor, and the law of total variance gives $v_{n+1}={\mu }^2{v}_n+{\sigma }^2{\mu }^n$, $v_0=0$. Iterating yields the branching-process generation momentsFor the critical case $\mu =1$, the correct limiting value is $v_n=n{\sigma }^2$. If $\mu =0$, nonnegative offspring are zero almost surely, so every later generation has zero mean and variance; handle this directly rather than use an ambiguous zero power. At generation zero the mean is one and variance zero.

The branching-process extinction criterion states that extinction probability is the smallest fixed point of $G$ in $[0,1]$: probabilities of extinction by successive generations are the iterates of $G$ from zero, increasing to that fixed point. Here the equation is $4q^3-7q+3=0$, factoring as $(q-1)(2q-1)(2q+3)=0$. The two admissible roots are $1/2$ and one, so

Let $q_n=\mathbb{P}(X_n=0)$ for a Galton-Watson process starting from one ancestor. Conditional on $X_1=k$, extinction by generation $n+1$ requires $k$ independent descendant processes to be extinct by generation $n$, soBecause zero is absorbing, $q_n\uparrow q$, the eventual extinction probability, and continuity gives $q=F(q)$. If $r\ge 0$ is any fixed point, monotonicity of $F$ and $q_0\le r$ give $q_n\le r$ inductively. Thus $q$ is the smallest nonnegative fixed point.

Here $F(s)=s/4+3s^3/4$. Every individual has at least one child, so $q=0$. The offspring mean is $F^{\prime }(1)=5/2$, hence

By Tonelli theorem,If $p<p_c$, part (a) bounds the summand by $e^{-c\Vert x{\Vert }_{\infty }}$. There are only polynomially many vertices at each radius, so the series converges and $\chi (p)<\infty$.

Conversely, suppose $\chi (p)<\infty$. Then $p<1$. Choose $q>p$ so close to $p$ thatUse the standard sprinkling coupling for Bernoulli percolation: first expose the $p$-open clusters, then independently open each remaining edge with probability $\alpha =(q-p)/(1-p)$. Explore the $q$-cluster of the origin cluster by following sprinkled edges. Each discovered $p$-cluster has at most $2d$ times its number of vertices as many incident edges, so the exploration is dominated by a Galton-Watson process of mean at most $2d\alpha \chi (p)<1$. This process dies out almost surely, and hence there is no infinite $q$-open cluster. Thus $q\le p_c$, and $p<q$ implies $p<p_c$. Therefore

Let $Z_n$ be the size of generation $n$. This is a Galton-Watson process with offspring meanThe expected generation size in a Galton-Watson process is thereforeIts probability generating function isBy the Galton-Watson extinction fixed point, the extinction probability $q$ is the smallest solution in $[0,1]$ of $G(q)=q$. Factoring givesso $q=(\sqrt{29}-5)/2$. The probability of production continuing forever is

The open descendants of any vertex form a Galton-Watson process with offspring distribution $\mathrm{Bin}(k,p)$. If $kp\le 1$, it dies out almost surely, so $N_{\infty }=0$.

If $kp>1$, let $\theta >0$ be its survival probability. At level $n$, each vertex begins an independent descendant subtree; the event that its edge to its parent is closed while its descendant open cluster is infinite has probability $(1-p)\theta >0$. Thus the number of such vertices at level $n$ is binomial with $k^n$ trials and a fixed positive success probability. For every fixed $M$, the probability of at least $M$ successes tends to one. Their infinite clusters are separated by their closed parent edges, so $\mathbb{P}(N_{\infty }\ge M)=1$ for every $M$, and hence $N_{\infty }=\infty$ almost surely.

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.