Galton–Watson branching processes in Lean

4.3 The joint form

Definition 4.6 The decoration of a skeleton vertex
✓

The decoration of a skeleton vertex is its offspring count \(j\), its number \(k\) of surviving children, and its dying subtrees indexed by rank.

Theorem 4.7 The joint Harris decomposition
✓

Conditioned on survival, probe the skeleton on a finite prefix-closed set \(F\) of addresses and constrain the decoration of each probed vertex. The mass factorises into one weight per vertex,

\[ \prod _{u\in F} \frac{\theta _{j_u}\binom {j_u}{k_u}(1-q)^{k_u}q^{\, j_u-k_u}}{1-q} \prod _{m{\lt}j_u-k_u}\mathbb {P}_{\hat\theta }(\mathcal{T}\in \mathcal{A}_{u,m}), \]

each dying subtree entering through the Galton–Watson law of the conjugate law.

Proof ▶

We first prove the factorisation at the root. Fix the root offspring count \(j\) and the set \(S\) of its \(k\) surviving children. Splitting the field at the root gives independent blocks: the root count has mass \(\theta _j\), the fields indexed by \(S\) have law \(\mathbb {P}^{\mathrm s}\), and the remaining fields have law \(\mathbb {P}^{\mathrm b}\). Summing over the \(\binom {j}{k}\) possible sets \(S\) and dividing by the survival probability \(1-q\) gives the root decoration weight in the statement.

We now induct on the maximal length of an address in \(F\). Since \(F\) is prefix-closed, it decomposes into the root and, for each child address occurring in \(F\), a prefix-closed set of suffixes. The compatibility assumption ensures that these children are among the first \(k_{\emptyset }\) surviving children. Apply the root factorisation, then apply the induction hypothesis independently inside each of the corresponding surviving subfields. The resulting products combine to give one decoration factor for every \(u\in F\). Finally, theorem 4.5 identifies the law of each dying subtree with the Galton–Watson law of \(\hat\theta \), yielding the displayed formula.