Galton–Watson branching processes in Lean

4.1 Conditioning at the root

Definition 4.1 The conditioned laws
✓

Write \(\mathbb {P}^{\mathrm{s}}\) for the field measure conditioned on survival and \(\mathbb {P}^{\mathrm{b}}\) for it conditioned on extinction. The skeleton degree of a field is the number of children of the root founding an infinite subtree.

Unconditionally, the root has exactly \(k\) surviving children with probability

\[ \sum _{j}\theta _j\binom {j}{k}(1-q)^{k}q^{\, j-k}, \]

and the value at \(k=0\) is \(f(q)=q\).

Proof ▶

Condition on the root having \(j\) children. For a fixed set \(S\) of these children, the branching property identifies the event that precisely the children in \(S\) survive with a product event for the \(j\) shifted fields. Its probability is

\[ \theta _j(1-q)^{\lvert S \rvert }q^{\, j-\lvert S \rvert }. \]

The events obtained from distinct sets \(S\) are disjoint. Summing over the \(\binom {j}{k}\) sets of size \(k\), and then over \(j\), gives the stated formula. When \(k=0\), the sum is \(\sum _j\theta _jq^j=f(q)=q\) by lemma 2.5.

Definition 4.3 The reduced and the conjugate law
✓

The reduced law is the Harris–Sevastyanov transform \(\tilde\theta _k=\bigl(\sum _j\theta _j\binom {j}{k}(1-q)^kq^{\, j-k}\bigr)/(1-q)\) for \(k\geq 1\) and \(\tilde\theta _0=0\); the conjugate law is \(\hat\theta _j=\theta _jq^{\, j}/q\). Both are offspring laws with the same support bound.

Proof ▶

All the displayed weights are nonnegative and vanish above \(J\). To compute the total surviving-child weight, interchange the two finite sums and apply the binomial theorem:

\[ \sum _{k=0}^{J}\sum _{j=k}^{J} \theta _j\binom {j}{k}(1-q)^kq^{j-k} =\sum _{j=0}^{J}\theta _j\sum _{k=0}^{j} \binom {j}{k}(1-q)^kq^{j-k} =\sum _{j=0}^{J}\theta _j((1-q)+q)^j=1. \]

By lemma 4.2, the term with \(k=0\) is \(q\). The terms with \(k\geq 1\) therefore sum to \(1-q\), and division by \(1-q\) proves that the reduced weights sum to one. For the conjugate weights,

\[ \sum _{j=0}^{J}\hat\theta _j=q^{-1}\sum _{j=0}^{J}\theta _jq^j =q^{-1}f(q)=1. \]