Branching Processes

(Lemma: generating function iteration.) We use the technique of conditioning on $Z_n$ and applying independence of offspring. Condition on $Z_n = k$. Given this event, $Z_{n+1} = \sum_{i=1}^k \xi_{n,i}$ is a sum of $k$ i.i.d. copies of $\xi$, independent of the history up to time $n$ (this is exactly the defining recursion). By the standard product rule for pgfs of sums of independent random variables,

Hence, by the law of total expectation,

This proves $\phi_{n+1} = \phi_n \circ \phi$. We now show separately that $\phi_n \circ \phi = \phi \circ \phi_n$, i.e. that composition in the other order also works, by induction on $n$. For $n=0$: $\phi_0(s) = \mathbb E[s^{Z_0}] = s$ since $Z_0 \equiv 1$, so $\phi_0(\phi(s)) = \phi(s) = \phi(\phi_0(s))$. Assume $\phi_n(\phi(s)) = \phi(\phi_n(s))$ for some $n$. Then using the recursion just derived twice,

and separately

by the inductive hypothesis applied inside. Since composition of functions is associative, $\phi_n(\phi(\phi(s))) = \phi(\phi(\phi_n(s)))$ trivially (both denote applying $\phi_n$ then $\phi\circ\phi$, versus $\phi\circ\phi$ then... to avoid confusion we verify directly): write $\psi = \phi\circ\phi$. By the base recursion $\phi_{n+1} = \phi_n\circ\phi$ applied with the whole process shifted, one instead argues more directly as follows. A cleaner induction: define $\phi_n$ as above and prove $\phi_n = \phi^{(n)}$ (the $n$-fold self-composition) directly by induction on $n$, which immediately gives both composition identities since $\phi^{(n)}\circ\phi = \phi\circ\phi^{(n)} = \phi^{(n+1)}$ for iterates of a single fixed function $\phi$ (iterates of one function always commute with themselves). Base case $n=0$: $\phi_0(s)=s=\phi^{(0)}(s)$. Inductive step: assuming $\phi_n = \phi^{(n)}$, the relation $\phi_{n+1} = \phi_n\circ\phi$ proved above gives

This completes the induction and proves $\phi_n = \phi^{(n)}$ for all $n$, from which both stated identities $\phi_{n+1}=\phi_n(\phi(s))=\phi(\phi_n(s))=\phi^{(n+1)}(s)$ follow immediately, the second equality because self-iterates of one function commute with one more application of that function on either side. $\blacksquare$

(Theorem, part 1: $q$ is the smallest fixed point of $\phi$.) We use the technique of monotone limits together with continuity of pgfs. Let $q_n = \Pr(Z_n = 0)$. Since $\{Z_0=0\}$ is impossible ($Z_0\equiv1$), $q_0 = 0$. The event $\{Z_n = 0\}$ implies $\{Z_{n+1}=0\}$, because $0$ is absorbing (if generation $n$ is already extinct, generation $n+1$ is too, as the empty sum is $0$). Hence $\{Z_n=0\}$ is an increasing sequence of events in $n$, so $q_n$ is non-decreasing, and

by continuity of probability measures along increasing unions. By the Lemma, $q_n = \Pr(Z_n=0) = \phi_n(0) = \phi^{(n)}(0)$, i.e. $q_n$ is obtained by starting at $0$ and applying $\phi$ $n$ times: $q_{n+1} = \phi(q_n)$, with $q_0=0$. Since $\phi$ is a power series with non-negative coefficients summing to $\phi(1)=1$, it is continuous on $[0,1]$ (indeed real-analytic on $[0,1)$ and continuous up to $s=1$ by Abel's theorem for power series with non-negative coefficients and finite value at $1$). Taking $n\to\infty$ in $q_{n+1}=\phi(q_n)$ and using continuity of $\phi$,

So $q$ is a fixed point of $\phi$ in $[0,1]$. To see $q$ is the smallest such fixed point, let $s^* \in [0,1]$ be any fixed point, $\phi(s^*) = s^*$. We show $q_n \le s^*$ for all $n$ by induction. Base case: $q_0 = 0 \le s^*$. Inductive step: if $q_n \le s^*$, then since $\phi$ is non-decreasing on $[0,1]$ (all coefficients $p_k \ge 0$, so $\phi'(s) = \sum_k k p_k s^{k-1} \ge 0$ for $s\in[0,1)$),

By induction $q_n \le s^*$ for all $n$, hence $q = \lim_n q_n \le s^*$. So $q$ is $\le$ every fixed point in $[0,1]$, i.e. $q$ is the smallest one. This proves part 1. $\blacksquare$

(Theorem, part 2 and 3: the role of $m = \phi'(1^-)$.) We use the technique of convexity analysis of $\phi$ on $[0,1]$. Since all $p_k \ge 0$ and $\phi(s) = \sum_k p_k s^k$, differentiating termwise (valid inside the radius of convergence, which is at least $1$ since $\sum p_k = 1$) gives

So $\phi$ is convex and non-decreasing on $[0,1)$, and by monotone convergence, $\phi'(s) \to \phi'(1^-) = m$ as $s\uparrow 1$ (allowing $m=\infty$ if the offspring distribution has infinite mean). Also $\phi(1) = \sum_k p_k = 1$, so $s=1$ is always a fixed point of $\phi$. We must determine whether there is a smaller fixed point in $[0,1)$, and the answer is governed by the slope of $\phi$ at $1$. Case $m \le 1$. We claim $\phi(s) > s$ for all $s \in [0,1)$, which forces the smallest fixed point in $[0,1]$ to be $s=1$ itself (if $\phi(s)>s$ throughout $[0,1)$, no point there can be a fixed point, so $q_n < 1$ for finite $n$ but the increasing sequence $q_n$ can only converge to the fixed point $1$, by part 1's characterization — more directly, since $q$ is a fixed point of $\phi$ by part 1, and no point in $[0,1)$ is a fixed point in this case, we must have $q=1$). To prove the claim, define $g(s) = \phi(s) - s$ on $[0,1]$. Then $g(1) = 0$ and $g'(s) = \phi'(s) - 1$. Since $\phi'$ is non-decreasing (as $\phi''\ge0$) and $\phi'(1^-) = m \le 1$, we get $\phi'(s) \le m \le 1$ for all $s \in [0,1)$, hence $g'(s) \le 0$ on $[0,1)$, so $g$ is non-increasing on $[0,1]$. Since $g(1)=0$ and $g$ is non-increasing, $g(s) \ge g(1) = 0$ for $s \le 1$, i.e. $\phi(s) \ge s$ for $s\in[0,1)$. We need the strict inequality $\phi(s) > s$ to rule out other fixed points. Suppose for contradiction $g(s_0) = 0$ for some $s_0 \in [0,1)$. Since $g$ is non-increasing and $g(s_0)=g(1)=0$, $g$ must be identically $0$ on $[s_0,1]$ (a non-increasing function that returns to its starting value must be constant on the interval). Then $g'(s) = 0$ for all $s\in(s_0,1)$, i.e. $\phi'(s) = 1$ identically there. Since $\phi'$ is non-decreasing and equals $1$ on this whole subinterval while $\phi'(1^-)=m\le1$, and $\phi'$ is analytic (a power series), $\phi'(s)\equiv 1$ forces $\phi'$ constant $=1$ on all of $[0,1)$ by analytic continuation (a power series agreeing with a constant on an interval has all higher coefficients zero). But $\phi'(s) = \sum_{k\ge1} kp_k s^{k-1}$; if this is identically $1$ then $p_1 = 1$ and $p_k=0$ for $k\ge2$, i.e. $\phi(s) = s$, meaning $\xi \equiv 1$ almost surely — excluded by our hypothesis $p_0+p_1<1$ (this hypothesis says $\Pr(\xi\ge2)>0$, incompatible with $\xi\equiv1$; note also $p_0<1$ rules out the other degenerate case separately handled). Contradiction. Hence no such $s_0$ exists, proving $\phi(s) > s$ strictly on $[0,1)$, and therefore $q=1$. Case $m > 1$. Now $\phi'(1^-) = m > 1$, so since $\phi'$ is continuous and non-decreasing near $1^-$ with limit $m>1$, there exists $\delta>0$ such that $\phi'(s) > 1$ for $s \in (1-\delta, 1)$, hence $g'(s) = \phi'(s)-1 > 0$ there, so $g$ is strictly increasing just to the left of $1$. Since $g(1)=0$, strict increase just before $1$ forces $g(s) < 0$, i.e. $\phi(s) < s$, for $s$ slightly less than $1$. On the other hand, $g(0) = \phi(0) - 0 = p_0 \ge 0$ (and $p_0<1$ by hypothesis, with the boundary case $p_0=0$ handled below). By the Intermediate Value Theorem applied to the continuous function $g$ on $[0,1]$, since $g(0) = p_0 \ge 0$ and $g(s)<0$ for some $s<1$ close to $1$, there exists a point $q^* \in [0,1)$ with $g(q^*) = 0$, i.e. $\phi(q^*) = q^*$. (If $p_0=0$ exactly, note $g(0)=0$ already gives a fixed point at $0$ itself, and the argument below shows it is not the smallest fixed point strictly less than $1$ is still attained since we need the smallest root; we handle uniqueness next which resolves this cleanly regardless.) We now show this fixed point in $[0,1)$ is unique, using strict convexity. Since $m>1$, $\phi$ is not the identity, so (as argued above) $\phi$ has at least one term $p_k>0$ for some $k\ge2$ or the mean could not exceed the $p_1$ coefficient alone in the required way — more directly: $\phi''(s) = \sum_{k\ge2}k(k-1)p_k s^{k-2}$, and if $\phi''\equiv 0$ on $[0,1)$ then $\phi$ is affine, $\phi(s)=p_0+p_1s$ with $p_0+p_1=1$, giving $m=p_1=1-p_0\le1$, contradicting $m>1$. So $\phi''(s)>0$ for some, hence (since it's a power series with non-negative coefficients) for all $s$ in some interval $(s_1,1)$, actually for all $s \in (0,1)$ once any coefficient $p_k>0$ for $k\ge 2$ is active, making $\phi$ strictly convex on $(0,1)$. A strictly convex function $\phi$ on $[0,1]$ with $\phi(1)=1$ can cross the line $y=s$ at most twice on $[0,1]$ (a strictly convex function minus a linear function, $g(s)=\phi(s)-s$, is itself strictly convex, and a strictly convex function has at most two zeros). We have exhibited one crossing at $s=1$ and one crossing at $q^*<1$; strict convexity of $g$ forbids a third, so $q^*$ is the unique fixed point in $[0,1)$. Finally we confirm $q = q^*$ using part 1 (smallest fixed point) together with monotonicity. Since $q$ is the smallest fixed point in $[0,1]$ by part 1, and the only fixed points are $q^*$ and $1$, with $q^*<1$, we conclude $q=q^*<1$. This proves parts 2 and 3. $\blacksquare$