# Branching Processes and Dwass’s Theorem

This is something I had to think about when writing my Part III essay, and it turns out to be relevant to some of the literature I’ve been reading this week. The main result is hugely helpful for reducing a potentially complicated combinatorial object to a finite sum of i.i.d. random variables, which in general we do know quite a lot about. I was very pleased with the proof I came up with while writing the essay, even if in the end it turned out to have appeared elsewhere before. (Citation at end)

Galton-Watson processes

A Galton-Watson process is a stochastic process describing a simple model for evolution of a population. At each stage of the evolution, a new generation is created as every member of the current generation produces some number of `offspring’ with identical and independent (both across all generations and within generations) distributions. Such processes were introduced by Galton and Watson to examine the evolution of surnames through history.

More precisely, we specify an offspring distribution, a probability distribution supported on $\mathbb{N}_0$. Then define a sequence of random variables $(Z_n,n\in\mathbb{N})$ by:

$Z_{n+1}=Y_1^n+\ldots+Y_{Z_n}^n,$

where $(Y_k^n,k\geq 1,n\geq 0)$ is a family of i.i.d. random variables with the offspring distribution $Y$. We say $Z_n$ is the size of the $n$th generation. From now on, assume $Z_0=1$ and then we call $(Z_n,n\geq 0)$ a Galton-Watson process. We also define the total population size to be

$X:=Z_0+Z_1+Z_2+\ldots,$

noting that this might be infinite. We refer to the situation where $X<\infty$ finite as extinction, and can show that extinction occurs almost surely when $\mathbb{E}Y\leq 1$, excepting the trivial case $Y=\delta_1$. The strict inequality parts are as you would expect. We say the process is critical if $\mathbb{E}Y=1$, and this is less obvious to visualise, but works equally well in the proof, which is usually driven using generating functions.

Total Population Size and Dwass’s Theorem

Of particular interest is $X$, the total population size, and its distribution. The following result gives us a precise and useful result linking the probability of the population having size $n$ and the distribution of the sum of $n$ RVs with the relevant offspring distribution. Among the consequences are that we can conclude immediately, by CLT and Cramer’s Large Deviations Theorem, that the total population size distribution has power-law decay in the critical case, and exponential decay otherwise.

Theorem (Dwass (1)): For a general branching process with a single time-0 ancestor and offspring distribution $Y$ and total population size $X$:

$\mathbb{P}(X=k)=\frac{1}{k}\mathbb{P}(Y^1+\ldots+ Y^k=k-1),\quad k\geq 1$

where $Y^1,\ldots,Y^k$ are independent copies of $Y$.

We now give a proof via a combinatorial argument. The approach is similar to that given in (2). Much of the literature gives a proof using generating functions.

Proof: For motivation, consider the following. It is natural to consider a branching process as a tree, with the time-0 ancestor as the root. Suppose the event $\{X=k\}$ in holds, which means that the tree has $k$ vertices. Now consider the numbers of offspring of each vertex in the tree. Since every vertex except the root has exactly one parent, and there are no vertices outside the tree, we must have $Y^1+\ldots+Y^k=k-1$ where $Y^1,\ldots,Y^k$ are the offspring numbers in some order. However, observe that this is not sufficient. For example, if $Y^1$ is the number of offspring of the root, and $k\geq 2$, then we must have $Y^1\geq 1$. Continue reading