Iterating the Offspring Generating Function

From One Generation to the Next

In a Galton–Watson branching process, each individual produces a random number of children, independently of all other individuals and according to the same offspring law. The generation-size distribution changes from one generation to the next, but its probability generating function can be updated by applying one fixed function: the generating function of the offspring count. Repeating this update gives the generating function at any generation.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((Z_n)_{n\ge0}\) be a discrete-time Galton–Watson process with state space \(S=\{0,1,2,\ldots\}\), started from one ancestor, so \(Z_0=1\). Each individual has a nonnegative integer-valued number of children with probability generating function \(f(s)=\mathbb{E}[s^\xi]\), where \(\xi\) is the offspring count and \(0\le s\le1\). Assume reproduction counts are independent across individuals and generations. Let \(\mathcal{F}_n\) record the reproduction through generation \(n-1\); then \(Z_n\) is \(\mathcal{F}_n\)-measurable, and the reproduction of individuals in generation \(n\) is independent of \(\mathcal{F}_n\).

For a nonnegative integer-valued random variable \(Y\), the convention \(s^0=1\), including at \(s=0\), makes its generating function \( \mathbb{E}[s^Y]\) well-defined throughout \([0,1]\). The branching assumption gives a direct way to calculate \(G_{n+1}\): condition on the current generation, and then account for the independent children of each individual.

Proof. Fix \(s\in[0,1]\). Given \(\mathcal{F}_n\), the current generation contains \(Z_n\) individuals. If their offspring counts are \(\xi_1,\ldots,\xi_{Z_n}\), then \(Z_{n+1}=\sum_{r=1}^{Z_n}\xi_r\). Conditional independence and the definition of \(f\) give \(\mathbb{E}[s^{Z_{n+1}}\mid\mathcal{F}_n]=f(s)^{Z_n}\). This also holds when \(Z_n=0\), because both sides are \(1\). Taking expectations yields \(G_{n+1}(s)=\mathbb{E}[f(s)^{Z_n}]=G_n(f(s))\). At generation \(0\), \(G_0(s)=\mathbb{E}[s^{Z_0}]=s=f^{\circ0}(s)\). If \(G_n=f^{\circ n}\), then \(G_{n+1}(s)=f^{\circ n}(f(s))\). Repeated composition of the same function is associative, so this equals \(f^{\circ(n+1)}(s)\). Induction proves the claim for all \(n\). \(\square\)

This proof explains the order of the update: the current population has generating function \(G_n\), and the offspring generated by each current individual contribute a factor \(f(s)\). Thus the update is \(G_{n+1}=G_n\circ f\). Because every function being composed is \(f\), the result is the \(n+1\)-fold iterate. The argument requires only that offspring counts be independent and identically distributed; it does not require a finite mean.

Proof. For \(m=0\), the identity is \(f^{\circ n}=f^{\circ0}\circ f^{\circ n}\), which holds because \(f^{\circ0}\) is the identity function. Suppose the identity holds for some \(m\). By the recursive definition of the iterates and associativity of function composition, \(f^{\circ(m+1+n)}=f\circ f^{\circ(m+n)}=f\circ(f^{\circ m}\circ f^{\circ n})=(f\circ f^{\circ m})\circ f^{\circ n}=f^{\circ(m+1)}\circ f^{\circ n}\). Induction proves the first statement. Substituting \(G_k=f^{\circ k}\), already proved, gives \(G_{m+n}=G_m\circ G_n\). \(\square\)

The generation-block identity says that evolving for \(n\) generations and then applying the same generation update for \(m\) more generations agrees with applying the update \(m+n\) times. It is an identity between generating functions; it does not say that generation sizes themselves are deterministic functions of their earlier values.

Worked Iterates for Standard Offspring Laws

What the Iteration Does—and Does Not—Mean

The iteration is a convenient way to represent the entire distribution of \(Z_n\), not just one summary of it. If \(G_n(s)=\sum_{k=0}^{\infty}\mathbb{P}(Z_n=k)s^k\), then its coefficients encode the probabilities at generation \(n\). For offspring laws whose generating functions are polynomials, composition can often be expanded to obtain the coefficients directly, as in the binomial example. For a rational or exponential generating function, leaving an iterate in nested form may be more useful than expanding it.

One can also start with a finite number \(r\) of ancestors. If the \(r\) ancestral family lines reproduce independently and each starts with the same offspring law, their generation-\(n\) population sizes are independent copies of the one-ancestor population size. The generating function of their sum is therefore \([f^{\circ n}(s)]^r\): for independent variables \(Y_1,\ldots,Y_r\), \(\mathbb{E}[s^{Y_1+\cdots+Y_r}]=\prod_{j=1}^r\mathbb{E}[s^{Y_j}]\). The one-ancestor formula is the special case \(r=1\).

Common mistake: multiplying instead of composing. The notation \(f^{\circ2}\) does not mean \(f(s)^2\). In the binomial example, take \(s=\tfrac12\). First, \(f(\tfrac12)=\frac{(1+\tfrac12)^2}{4}=\frac{9}{16}\). The correct second iterate is \(f(f(\tfrac12))=f(\tfrac{9}{16})=\frac{(1+\tfrac{9}{16})^2}{4}=\frac{(25/16)^2}{4}=\frac{625}{1024}\). The incorrect ordinary square would be \(f(\tfrac12)^2=(\tfrac{9}{16})^2=\frac{81}{256}=\frac{324}{1024}\). Since \(\frac{625}{1024}\ne\frac{324}{1024}\), the two operations give different answers. The correction is to substitute the whole function value into \(f\) at every iteration.

A practical calculation should keep three checks in view. First, begin with the offspring generating function for the stated law. Second, form the next iterate by substitution, not multiplication. Third, verify that each resulting generating function has value \(1\) at \(s=1\). When a polynomial is expanded, its coefficients should also be nonnegative and sum to \(1\); for an unexpanded expression, checking its value at \(1\) is a useful consistency check, though it does not by itself verify every coefficient.