---
title: "Probability Generating Functions"
book: "University Mathematics — Year 2"
subject: math
language: en
chapter: 23
exercises: 12
source: https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions
---

# Chapter 23 — Probability Generating Functions

The power series of [Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries) return with a probabilistic mission: to an $\N$-valued [random variable](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) we attach the power series with coefficients $\P(X = n)$. This *[generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci)* converts sums of [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) variables into products, moments into derivatives at $1$, and hard combinatorial identities into one-line multiplications. The chapter closes the book with two showpieces: the Poisson approximation of rare [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space), and the extinction criterion for branching processes — a genuinely infinite probabilistic computation solved entirely by the geometry of a convex curve.

## 23.1 Definition and basic properties

**Definition 23.1 (Probability generating function).**

Let $X$ be an $\N$-valued [random variable](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law), $p_n = \P(X = n)$. The *probability generating function* of $X$ is the sum of the power series

$$
G_X(t) = \E\bigl(t^X\bigr) = \sum_{n=0}^{\infty} p_n\,t^n .
$$

**Example 23.2 (First reflexes).**

A constant variable $X = c$ has $G_X(t) = t^c$; a shift obeys $G_{X+c}(t) = t^c\,G_X(t)$; and evaluating at special points reads off information without any expansion: $G_X(0) = \P(X
= 0)$, $G_X(1) = 1$, and $G_X(-1) = \P(X\text{ even}) -
\P(X\text{ odd})$, the parity balance exploited in [Exercise 23.10](#exo-b2-genfun-10). These one-liners are used silently everywhere below — and the evaluation $G_X(0)$ is exactly how extinction probabilities will be extracted from iterated [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) at the end of the chapter.

**Proposition 23.3 (Radius and first properties).**

The series defining $G_X$ has [radius of convergence](https://one-course.com/books/math/4/en/chapter/11-power-series#def-b2-powerseries-radius) $\geq 1$; $G_X$ is defined and [continuous](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) on $\intcc{-1}{1}$, $\mathcal{C}^\infty$ on $\intoo{-1}{1}$, with $G_X(1) = 1$ and $\abs{G_X(t)} \leq 1$ there. Moreover $G_X$ determines the [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of $X$:

$$
p_n = \frac{G_X^{(n)}(0)}{n!} .
$$

**Proof.** Since $\sum p_n = 1$ converges, the terms $p_n\,1^n$ are bounded, so the radius is $\geq 1$ (Abel’s lemma, [Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)); at $t = \pm1$ the series converges [absolutely](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-def) ($\sum p_n = 1$ dominates); better, on the whole interval $\intcc{-1}1$,

$$
\sup_{\abs t\leq1}\,\abs{p_nt^n} = p_n
\quad\text{with}\quad \sum_np_n < \infty :
$$

the series converges *[normally](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-series)* on $\intcc{-1}1$, so its sum is [continuous](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) there (Theorems [10.16](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#thm-b2-funcseq-weierstrass) and [10.4](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#thm-b2-funcseq-continuity)). Smoothness inside and the coefficient formula are the general theory of power series; the coefficients being recoverable, two variables with the same [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) have the same [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law). ∎

**Example 23.4 (The classical laws).**

- Bernoulli $\mathcal{B}(p)$ : $G(t) = 1 - p + pt$ .
- Binomial $\mathcal{B}(n, p)$ : $G(t) = \sum_k \binom nk (pt)^k(1-p)^{n-k} = (1 - p + pt)^n$ (binomial theorem).
- Geometric $\mathcal{G}(p)$ : $G(t) = \sum_{k\geq1}(1-p)^{k-1}p\,t^k = \dfrac{pt}{1 - (1-p)t}$ (radius $\frac{1}{1-p} > 1$ ).
- Poisson $\mathcal{P}(\lambda)$ : $G(t) = \sum_k e^{-\lambda}\frac{(\lambda t)^k}{k!} = e^{\lambda(t - 1)}$ (radius $\infty$ ).

**Example 23.5 (Integrating the generating function).**

Derivatives of $G_X$ at $1$ give positive moments; the *integral* gives a negative one. From $\int_0^1t^k\dd t
= \frac1{k+1}$ and term-by-term integration ([normal convergence](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-series) on $\intcc01$):

$$
\int_0^1G_X(t)\,\dd t = \sum_{k\geq0}\frac{\P(X =
k)}{k+1} = \E\Bigl(\frac1{1+X}\Bigr).
$$

For $X \sim \mathcal P(\lambda)$:

$$
\E\Bigl(\frac1{1+X}\Bigr) =
\int_0^1\eu^{\lambda(t-1)}\,\dd t = \frac{1 -
\eu^{-\lambda}}{\lambda},
$$

recovering in one line the series computation of [Example 22.10](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ex-b2-randomvar-transferex). The [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) is a two-way instrument: differentiate at $1$ for the moments $\E(X)$, $\E(X(X-1))$, integrate over $\intcc01$ for $\E\bigl(\frac1{1+X}\bigr)$ — one [analytic](https://one-course.com/books/math/4/en/chapter/11-power-series#def-b2-powerseries-analytic) object, queried in whichever direction the problem needs.

**Example 23.6 (A law with radius exactly one).**

Let $\P(X = k) = \dfrac{6}{\pi^2k^2}$ for $k \geq 1$ — a probability [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) by Basel’s identity ([Example 14.12](https://one-course.com/books/math/4/en/chapter/14-fourier-series#ex-b2-fourier-basel)). Its [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $G(t) = \frac6{\pi^2}\sum_{k\geq1}\frac{t^k}{k^2}$ has [radius of convergence](https://one-course.com/books/math/4/en/chapter/11-power-series#def-b2-powerseries-radius) exactly $1$: the general bound “radius $\geq
1$” of [Proposition 23.3](#prop-b2-genfun-radius) cannot be improved. And the mean is

$$
\sum_{k\geq1}k\,\P(X = k) =
\frac6{\pi^2}\sum_{k\geq1}\frac1k = \infty :
$$

$G$ is [continuous](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) on $\intcc{-1}1$, smooth inside, but its derivative blows up at $1^-$ — the graph arrives at the point $(1, 1)$ with a vertical tangent. Heavy tails are visible *geometrically* on the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci), at the single point $t = 1$; the moments theorem below makes this correspondence exact.

**Theorem 23.7 (Moments from the generating function).**

$X$ has an [expectation](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation) if and only if $G_X$ is [differentiable](https://one-course.com/books/math/4/en/chapter/15-differential-calculus#def-b2-diffcalc-differential) at $1^-$ (left derivative, finite), and then $\E(X) = G_X'(1)$. Similarly $X$ has a second moment iff $G_X$ is twice [differentiable](https://one-course.com/books/math/4/en/chapter/15-differential-calculus#def-b2-diffcalc-differential) at $1^-$, and then

$$
\E\bigl(X(X - 1)\bigr) = G_X''(1),
\qquad
V(X) = G_X''(1) + G_X'(1) - G_X'(1)^2 .
$$

**Proof.** For $t \in \intoo{0}{1}$, term-by-term differentiation inside the disk gives $G_X'(t) = \sum_{n\geq1} np_n t^{n-1}$, a series with nonnegative coefficients: $t \mapsto G_X'(t)$ is nondecreasing on $\intoo{0}{1}$, and by monotone convergence of partial sums (or Abel’s theorem for nonnegative coefficients, [Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)),

$$
\lim_{t \to 1^-} G_X'(t)
= \sum_{n\geq1} n\,p_n \in \intcc{0}{+\infty} ,
$$

each side finite exactly when the other is. When finite, the mean value theorem squeezes the difference quotients $\frac{G_X(1) -
G_X(t)}{1 - t}$ between values of $G_X'$, so $G_X$ is [differentiable](https://one-course.com/books/math/4/en/chapter/15-differential-calculus#def-b2-diffcalc-differential) at $1^-$ with $G_X'(1) = \sum np_n = \E(X)$ (by transfer). The second-order statement repeats the argument one level up: $G''_X(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ is nondecreasing on $\intoo01$ with monotone limit $\sum_nn(n-1)p_n = \E(X(X-1))$, finite exactly when $X$ has a second moment. The [variance](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-variance) formula then follows from König–Huygens:

$$
V(X) = \E(X^2) - \E(X)^2 = \E\bigl(X(X-1)\bigr) + \E(X) -
\E(X)^2 = G''_X(1) + G'_X(1) - G'_X(1)^2 .
$$

∎

**Example 23.8.**

Poisson: $G'(t) = \lambda e^{\lambda(t-1)}$, so $\E(X) = \lambda$; $G''(1) = \lambda^2$, so $V(X) = \lambda^2 + \lambda - \lambda^2 =
\lambda$ — the computations of [Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar) in one line each.

**Example 23.9 (The mode of a Poisson law).**

Where is $\P(X = k)$ largest for $X \sim \mathcal
P(\lambda)$? Consecutive weights compare through the ratio

$$
\frac{\P(X = k+1)}{\P(X = k)} = \frac{\lambda}{k + 1} ,
$$

which exceeds $1$ while $k < \lambda - 1$ and drops below $1$ once $k > \lambda - 1$: the weights rise then fall, with mode $\floor\lambda$ (and a tie between $\lambda - 1$ and $\lambda$ when $\lambda$ is an integer: for $\lambda = 3$, $\P(X = 2) = \P(X = 3) = \frac92\eu^{-3} \approx 0.224$). Ratio tests on the coefficients are often the fastest route to qualitative facts about a discrete [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) — no [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) needed, but the coefficients *are* the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci), read term by term.

## 23.2 Sums of independent variables

**Theorem 23.10 (Multiplicativity).**

If $X$ and $Y$ are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) $\N$-valued [random variables](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law), then

$$
G_{X + Y}(t) = G_X(t)\,G_Y(t)
\qquad (\abs t \leq 1),
$$

and by induction $G_{X_1 + \dots + X_n} = \prod_i G_{X_i}$ for [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) $X_1, \dots, X_n$.

**Proof.** Two proofs, both instructive. *Via [expectations](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation):* $t^X$ and $t^Y$ are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) bounded variables, so ([Theorem 22.11](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#thm-b2-randomvar-product))

$$
G_{X+Y}(t) = \E\bigl(t^{X+Y}\bigr)
= \E\bigl(t^X t^Y\bigr)
= \E\bigl(t^X\bigr)\E\bigl(t^Y\bigr) .
$$

*Via [Cauchy products](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#thm-b2-series-fubini):* the [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of $X + Y$ is the convolution $\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k)$, and the [Cauchy product](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#thm-b2-series-fubini) theorem for [absolutely](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-def) convergent series ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)) multiplies the two power series exactly along this convolution. ∎

**Example 23.11 (Stability of the classical laws).**

[Independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) binomials with the same $p$ add: $(1 - p + pt)^m(1 -
p + pt)^n = (1 - p + pt)^{m+n}$, so $\mathcal{B}(m, p) +
\mathcal{B}(n, p) = \mathcal{B}(m + n, p)$ — in particular a sum of $n$ [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) Bernoulli variables is binomial, re-proving the [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of the number of successes. [Independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) Poissons add: $e^{\lambda(t-1)}e^{\mu(t-1)} = e^{(\lambda + \mu)(t-1)}$, so $\mathcal{P}(\lambda) + \mathcal{P}(\mu) = \mathcal{P}(\lambda +
\mu)$ — the convolution computation of [Exercise 22.2](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#exo-b2-randomvar-2), now without computation.

**Example 23.12 (Two dice, one polynomial squared).**

For one fair die, $G(t) = \frac{t + t^2 + \dots + t^6}{6}$; for the sum of two,

$$
G(t)^2 = \frac{1}{36}\bigl(t^2 + 2t^3 + 3t^4 + 4t^5 + 5t^6 +
6t^7 + 5t^8 + 4t^9 + 3t^{10} + 2t^{11} + t^{12}\bigr) :
$$

the triangular [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of dice sums ($7$ is the mode, with probability $\frac6{36} = \frac16$), read off a polynomial square that one multiplies out once in a lifetime. The convolution formula would have required eleven separate counting arguments; the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) does them all simultaneously, because multiplying polynomials *is* convolving coefficients. This mechanical translation — [laws](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) to coefficients, sums to products — is the whole business model of the chapter, and [Exercise 23.11](#exo-b2-genfun-11) pushes it to the surprising Sicherman dice.

**Example 23.13 (Three dice and a coefficient extraction).**

For the sum $S$ of three fair dice, $\P(S = 10)$ is the coefficient of $t^{10}$ in $\bigl(\frac{t + \dots +
t^6}6\bigr)^3$. Factor and expand with the binomial and geometric series:

$$
\Bigl(\frac{t(1 - t^6)}{6(1 - t)}\Bigr)^{\!3}
= \frac{t^3}{216}\,\bigl(1 - 3t^6 + 3t^{12} -
t^{18}\bigr)\sum_{j\geq0}\binom{j+2}2t^j .
$$

The coefficient of $t^{10}$ requires $t^7$ from the product: $j = 7$ with the term $1$, and $j = 1$ with the term $-3t^6$:

$$
\P(S = 10) = \frac{1}{216}\Bigl(\binom92 -
3\binom32\Bigr) = \frac{36 - 9}{216} = \frac{27}{216} =
\frac18 .
$$

Direct enumeration of the $27$ triples is error-prone; the algebra is mechanical and scales to any number of dice — the inclusion–exclusion visible in $(1 - t^6)^3$ is doing the case analysis automatically.

**Example 23.14 (Reading a law off its generating function).**

Which [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) has $G(t) = \dfrac1{2 - t}$? Expand into a power series:

$$
\frac{1}{2 - t} = \frac12\cdot\frac1{1 - t/2}
= \sum_{k\geq0}\frac{t^k}{2^{k+1}} :
$$

nonnegative coefficients summing to $G(1) = 1$, so this is a genuine [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law), $\P(X = k) = 2^{-(k+1)}$ on $\N$ — a geometric [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) starting at $0$. By uniqueness ([Proposition 23.3](#prop-b2-genfun-radius)), no other [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) shares this $G$. Recognizing [laws](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) from their [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) is a skill worth drilling: it is how the critical branching iterate $G_n(t) = \frac{n - (n-1)t}{n+1 - nt}$ of the weekend problem is unmasked as a geometric [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) conditioned on survival.

**Remark 23.15.**

Stability goes one way only: sums of [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) Poissons are Poisson, but differences are not — $X - Y$ takes negative values, so it has no [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) at all, and its [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) (the Skellam [distribution](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law)) lies outside this chapter’s toolkit. Likewise $\mathcal B(m, p) + \mathcal B(n, p')$ with $p \neq p'$ is *not* binomial: the product $(1 - p +
pt)^m(1 - p' + p't)^n$ has two distinct root locations, while every binomial pgf has a single repeated root. Reading stability off root patterns is a small preview of how much structure the polynomial encodes.

**Remark 23.16 (The roots-of-unity filter).**

Evaluating at $-1$ separates even from odd; evaluating at all $m$-th roots of unity separates every residue class: with $\omega = \eu^{2\iu\pi/m}$,

$$
\P(X \equiv r \bmod m)
= \frac1m\sum_{j=0}^{m-1}\omega^{-jr}\,G_X(\omega^j),
$$

since averaging $\omega^{j(k-r)}$ over $j$ yields $1$ if $k
\equiv r$ and $0$ otherwise. Sample dividend: for the sum $S$ of two fair dice, each $G(\omega^j) = \frac16\sum_{k=1}^6
\omega^{jk} = -\frac16$ for $j \neq 0$ (the seven seventh roots of unity sum to zero), so

$$
\P(7 \mid S) = \frac17\Bigl(1 +
6\cdot\frac1{36}\Bigr) = \frac16 ,
$$

confirming the count from [Example 23.12](#ex-b2-genfun-twodice) — and the method scales to questions where direct counting does not.

**Theorem 23.17 (Random sums: Wald’s identity for generating functions).**

Let $(X_k)_{k\geq1}$ be [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) $\N$-valued variables with the same [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) and [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $G_X$, and let $N$ be an $\N$-valued variable [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) of the $X_k$, with [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $G_N$. Then the random sum $S = X_1 + \dots + X_N$ (with $S = 0$ when $N = 0$) has [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci)

$$
G_S = G_N \circ G_X .
$$

In particular, if $N$ and $X_1$ have [expectations](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation), $\E(S) =
\E(N)\,\E(X_1)$.

**Proof.** Condition on $N$ (total probability, [Theorem 21.14](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-bayes)): for $\abs t \leq 1$,

$$
G_S(t) = \sum_{n=0}^\infty \P(N = n)\,
\E\bigl(t^{X_1 + \dots + X_n}\bigr)
= \sum_{n=0}^\infty \P(N = n)\,G_X(t)^n
= G_N\bigl(G_X(t)\bigr),
$$

using multiplicativity for each fixed $n$ and the [summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) of the whole double family ($\abs{G_X(t)} \leq 1$). The exchange of summations is Fubini for [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) families ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)). Differentiating at $1^-$ by the chain rule and [Theorem 23.7](#thm-b2-genfun-moments): $\E(S) = G_N'(G_X(1))\,G_X'(1)
= G_N'(1)G_X'(1) = \E(N)\E(X_1)$. ∎

**Example 23.18 (Compound Poisson: yearly insurance losses).**

An insurer receives $N \sim \mathcal P(\lambda)$ claims in a year, each claim costing $X_k$ (integer units, i.i.d., pgf $G_X$, mean $\mu$, independent of $N$). By [Theorem 23.17](#thm-b2-genfun-compound), the total loss $S$ has

$$
G_S(t) = \eu^{\lambda(G_X(t) - 1)},
\qquad
\E(S) = \lambda\mu ,
$$

and differentiating twice at $1^-$:

$$
V(S) = \lambda\,G_X''(1) + \lambda^2\mu^2 + \lambda\mu -
(\lambda\mu)^2 = \lambda\,\E(X^2) .
$$

The [variance](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-variance) involves the *second* moment of a single claim, not its [variance](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-variance): a compound Poisson sum feels the occasional large claim twice — once through how many, once through how big. For $\lambda = 10$ claims of geometric [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) with mean $2$ ($\E X^2 = 6$): $\E S = 20$, $V(S) = 60$, and Chebyshev ([Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar)) already yields usable solvency margins. This “randomly stopped sum” pattern is the same one that will drive the branching recursion of [Proposition 23.23](#prop-b2-genfun-branching): composition of [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) is the algebra of random populations.

**Remark 23.19.**

The [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) of $N$ from the summands is not decorative. Take $X_k \in \{0, 2\}$ with equal probabilities and let $N =
X_1$ (flagrantly dependent): then $S = X_1 + \dots + X_N$ is $0$ when $X_1 = 0$, and $2 + X_2$ when $X_1 = 2$, so $\E(S) =
\frac12(2 + 1) = \frac32$, while $\E(N)\E(X_1) = 1\cdot1 =
1$: Wald’s identity fails. When the number of terms is allowed to *react* to the terms themselves, the clean product structure collapses — the full theory of such “stopping” rules is the martingale chapter of the Year 3 volume.

## 23.3 Poisson approximation

**Theorem 23.20 (Law of rare events).**

Let $X_n \sim \mathcal{B}(n, p_n)$ with $n\,p_n \to \lambda > 0$. Then for every $k \in \N$:

$$
\P(X_n = k)
\xrightarrow[n\to\infty]{}
e^{-\lambda}\frac{\lambda^k}{k!} :
$$

the binomial [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of many rare [independent events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) converges to the Poisson [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of parameter $\lambda$.

**Proof.** Direct computation with $p_n = \frac{\lambda_n}{n}$, $\lambda_n
\to \lambda$:

$$
\P(X_n = k)
= \binom nk p_n^k(1 - p_n)^{n-k}
= \frac{n(n-1)\cdots(n-k+1)}{n^k}\cdot
\frac{\lambda_n^k}{k!}\,
\bigl(1 - \tfrac{\lambda_n}{n}\bigr)^{n-k} .
$$

As $n \to \infty$ with $k$ fixed: the first factor tends to $1$ (product of $k$ factors $\to 1$); $\lambda_n^k \to \lambda^k$; and $\bigl(1 - \frac{\lambda_n}{n}\bigr)^{n-k} =
\exp\bigl((n-k)\ln(1 - \frac{\lambda_n}{n})\bigr) \to
e^{-\lambda}$ since $(n - k)\ln\bigl(1 - \frac{\lambda_n}{n}\bigr)
\sim -\lambda_n \to -\lambda$ ([Chapter 6](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ch-b2-comparison)). Alternatively, at the level of [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci): $G_{X_n}(t) = \bigl(1 +
\frac{\lambda_n(t-1)}{n}\bigr)^n \to e^{\lambda(t - 1)} =
G_{\mathcal{P}(\lambda)}(t)$ for each fixed $t \in [0, 1]$ — convergence of [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci), which (for $\N$-valued variables) is equivalent to convergence of each $\P(X_n = k)$; see [Exercise 23.9](#exo-b2-genfun-9). ∎

**Remark 23.21.**

This is why Poisson [laws](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) model counts of rare [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) — typos per page, radioactive decays per second, accidents per day at a crossing: each opportunity is nearly negligible, opportunities are many, and only the mean rate $\lambda$ survives in the limit.

**Example 23.22 (Watching the Poisson limit converge).**

Fix $\lambda = 2$ and let $X_n \sim \mathcal B(n, 2/n)$. The [no-event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) probability is exactly $\P(X_n = 0) = (1 - 2/n)^n$:

$$
n = 10:\ 0.107, \qquad
n = 20:\ 0.122, \qquad
n = 50:\ 0.130, \qquad
n = 100:\ 0.133,
$$

against the limit $\eu^{-2} \approx 0.135$. The convergence is monotone and of speed $O(1/n)$ — expanding, $(1 -
2/n)^n = \eu^{-2}\bigl(1 - \tfrac2n + O(n^{-2})\bigr)$ — so for $n$ in the hundreds the Poisson model is already accurate to the third digit. This is the practical content of the law of rare events: the modeller never knows $n$ and $p$ separately (how many micro-opportunities for a typo does a page hold?), but only their product $\lambda$, and the limit [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) mercifully depends on nothing else.

## 23.4 Branching processes

Consider a population starting from one ancestor; each individual, independently, has a random number of children with [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $(p_k)_{k
\in \N}$ and [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $G$ (the *offspring [distribution](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law)*). Let $Z_n$ be the size of generation $n$ ($Z_0 =
1$), and let $m = G'(1) = \E(Z_1)$ be the mean offspring number.

**Proposition 23.23.**

The [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) of $Z_n$ is the $n$-th iterate $G_{Z_n} = G \circ G \circ \dots \circ G$ ($n$ times), and the extinction probabilities $q_n = \P(Z_n = 0)$ satisfy

$$
q_0 = 0, \qquad q_{n+1} = G(q_n),
$$

and increase to the probability $q$ of eventual extinction, which is a fixed point of $G$.

**Proof.** Generation $n + 1$ is the random sum of the offspring of the $Z_n$ members of generation $n$, with counts [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) of each other and of $Z_n$: [Theorem 23.17](#thm-b2-genfun-compound) gives $G_{Z_{n+1}} =
G_{Z_n} \circ G$, and induction from $G_{Z_0}(t) = t$ yields the $n$-fold iterate — which, by associativity of composition, can equally be read as $G_{Z_{n+1}} = G \circ G_{Z_n}$. Evaluating this second form at $0$: $q_{n+1} = G_{Z_{n+1}}(0) =
G\bigl(G_{Z_n}(0)\bigr) = G(q_n)$. The [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\{Z_n = 0\}$ increase (extinct populations stay extinct), so $q_n \uparrow q = \P\bigl(\bigcup_n\{Z_n = 0\}\bigr)$ by monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ([Theorem 21.6](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-continuity)), and [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) of $G$ on $[0, 1]$ turns $q_{n+1} = G(q_n)$ into $q =
G(q)$ at the limit. ∎

**Example 23.24 (Watching extinction converge).**

For the offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $(p_0, p_1, p_2) = (\tfrac14,
\tfrac14, \tfrac12)$ of [Example 23.27](#ex-b2-genfun-branchingexample), $G(t) = \tfrac14 + \tfrac14t + \tfrac12t^2$ and the iteration $q_{n+1} = G(q_n)$ gives

$$
q_1 = 0.25, \quad q_2 = 0.34375, \quad q_3 \approx 0.39502,
\quad q_4 \approx 0.42678, \quad q_5 \approx 0.44776,
$$

climbing toward the extinction probability $q = \tfrac12$. The gaps $q - q_n$ are $0.25$, $0.156$, $0.105$, $0.073$, $0.052$: each is roughly $\tfrac34$ of the previous, and indeed the mean value theorem gives $q - q_{n+1} = G'(c_n)(q
- q_n)$ with $G'(q) = \tfrac14 + q = \tfrac34$. Two morals: a family line still alive at generation $n$ has, built into the same computation, probability $q - q_n$ of being doomed later; and the convergence rate of the staircase in the figure below is the derivative at the fixed point — the weekend problem turns both observations into theorems.

**Theorem 23.25 (Extinction criterion).**

Assume $p_1 \neq 1$. The extinction probability $q$ is the *smallest* fixed point of $G$ in $\intcc{0}{1}$, and:

- if $m \leq 1$ (subcritical or critical), $q = 1$ : extinction is certain;
- if $m > 1$ (supercritical), $q < 1$ : the population survives forever with positive probability $1 - q$ .

**Proof.** $G$ is [convex](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-convex) on $\intcc{0}{1}$ (power series with nonnegative coefficients: $G'' \geq 0$), nondecreasing, with $G(1) = 1$.

*Smallest fixed point:* let $r \in \intcc{0}{1}$ be any fixed point. Then $q_0 = 0 \leq r$, and inductively $q_{n+1} = G(q_n)
\leq G(r) = r$ (monotonicity): so $q = \lim q_n \leq r$.

*Case $m \leq 1$:* suppose $r < 1$ is a fixed point. By the mean value theorem on $[r, 1]$, there is $c \in \intoo{r}{1}$ with $G'(c) = \frac{G(1) - G(r)}{1 - r} = \frac{1 - r}{1 - r} = 1$. But $G'$ is nondecreasing (convexity) with $\lim_{t\to1^-}G'(t) = m
\leq 1$, so $G' \leq 1$ on $\intoo{0}{1}$; the equality $G'(c) =
1$ then forces $G'$ to be constant equal to $1$ on $\intco{c}{1}$, hence $G'' = \sum n(n-1)p_nt^{n-2} \equiv 0$ there. A power series with nonnegative coefficients vanishing on an interval has all these coefficients zero: $p_n = 0$ for $n \geq 2$, so $G(t) = p_0
+ p_1t$ and $1 = G'(c) = p_1$ — contradicting the hypothesis $p_1 \neq 1$. So $1$ is the only fixed point: $q = 1$.

*Case $m > 1$:* near $1$, $G(t) - t$ has derivative $G'(t) -
1 \to m - 1 > 0$ as $t \to 1^-$, so $G(t) - t < G(1) - 1 = 0$ on some interval $\intoo{1 - \delta}{1}$: the [continuous](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) function $G(t) - t$ is $\geq 0$ at $t = 0$ ($G(0) = p_0 \geq 0$) and $< 0$ just below $1$, so it vanishes at some $r < 1$ (intermediate value theorem). The smallest fixed point is then $q \leq r < 1$. ∎

![Extinction probabilities as a fixed-point iteration q_n+1 = G(q_n) starting at q_0 = 0 (red staircase). Left: a subcritical offspring law — the convex curve stays above the diagonal, the iteration climbs to the unique fixed point 1. Right: a supercritical law — the curve crosses the diagonal at q < 1, where the iteration stops: survival has probability 1 - q > 0.](https://one-course.com/images/onecourse/chapters/math-4/b2-genfun/fig-b000951f5d4d.svg)

![Extinction probabilities as a fixed-point iteration q_n+1 = G(q_n) starting at q_0 = 0 (red staircase). Left: a subcritical offspring law — the convex curve stays above the diagonal, the iteration climbs to the unique fixed point 1. Right: a supercritical law — the curve crosses the diagonal at q < 1, where the iteration stops: survival has probability 1 - q > 0.](https://one-course.com/images/onecourse/chapters/math-4/b2-genfun/fig-126f02aa14b3.svg)

***Figure 23.1.** Extinction probabilities as a fixed-point iteration $q_{n+1} = G(q_n)$ starting at $q_0 = 0$ (red staircase). Left: a subcritical offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) — the convex curve stays above the diagonal, the iteration climbs to the unique fixed point $1$. Right: a supercritical [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) — the curve crosses the diagonal at $q < 1$, where the iteration stops: survival has probability $1 -
q > 0$.*

**Remark 23.26 (How to read the cobweb).**

In the figure, a vertical move applies $G$ (from $(q_n, q_n)$ up to $(q_n, G(q_n))$), a horizontal move to the diagonal converts output into input: the staircase *is* the recursion $q_{n+1} = G(q_n)$. Convexity of $G$ and $G(1) = 1$ leave only two geometries. Either the curve stays above the diagonal on $\intco01$ (mean $m \leq 1$): the staircase has nowhere to stop before $1$. Or the curve crosses at some $q <
1$ ($m > 1$): the staircase is trapped below the crossing and converges to it, at the geometric rate $G'(q) < 1$ quantified in [Example 23.24](#ex-b2-genfun-cobwebnumerics). All the analysis of the extinction theorem is visible in this one picture — which is why it is worth drawing before computing.

**Example 23.27.**

Offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law): no child, one child, two children with probabilities $\frac14, \frac14, \frac12$. Then $m = \frac14 + 1 =
\frac54 > 1$ and $G(t) = \frac14 + \frac14 t + \frac12 t^2$. Fixed points: $\frac12 t^2 - \frac34 t + \frac14 = 0$, i.e. $2t^2 - 3t
+ 1 = (2t - 1)(t - 1) = 0$: $q = \frac12$. The family line dies out with probability $\frac12$ — and with probability $\frac12$ it lives forever.

**Remark 23.28 (Perspectives within this volume).**

The chapter is the book’s crossroads, and each ingredient arrived from a named place: the series algebra from [Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series) and [Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries), the probability from [Chapter 21](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#ch-b2-proba) (monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) proves $q_n \uparrow q$) and [Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar) ($G_X =
\E(t^X)$ is an [expectation](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation), multiplicativity is the product theorem), the convexity from [Chapter 8](https://one-course.com/books/math/4/en/chapter/8-functions-of-a-real-variable#ch-b2-realfun) through [Chapter 17](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#ch-b2-affine). Even the heavy-tail pathologies connect: the St Petersburg variable of the previous chapter has $G(t) = \sum_k2^{-k}t^{2^k}$, a perfectly convergent series on $\intcc01$ whose derivative at $1^-$ diverges — infinite mean, visible at a glance. One object, every tool of the year: a fitting last chapter.

**Remark 23.29 (Common pitfalls).**

(i) [Generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) apply to $\N$-valued variables only: for signed or non-integer variables the object $\E(t^X)$ loses its power-series structure (Year 3 replaces it with transforms adapted to $\R$). (ii) The first sanity check of any computed $G$ is $G(1) = 1$; the second is that the coefficients are nonnegative — a negative coefficient means an algebra slip, not a new [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law). (iii) In random sums, the composition order matters: $G_S = G_N \circ G_X$, the *outer* function counting the terms; composing the other way is meaningless ($G_X \circ G_N$ would count items of items). (iv) Multiplicativity needs [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) and distinct sources of randomness: $G_{2X}(t) = G_X(t^2)$, not $G_X(t)^2$. (v) Differentiating at $1$ is a boundary operation: when the radius is exactly $1$, as in [Example 23.6](#ex-b2-genfun-heavytail), $G'(1^-)$ may be infinite, and the moments theorem’s monotone-limit formulation is not a pedantic nicety but the honest statement.

## Closing the volume

The [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) is a fitting final object for this book: it is simultaneously a power series ([Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)), a tool of [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) families ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)), an [expectation](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation) ([Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar)), a convex function whose geometry decides extinction ([Chapter 8](https://one-course.com/books/math/4/en/chapter/8-functions-of-a-real-variable#ch-b2-realfun)), and a fixed-point iteration ([Chapter 4](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#ch-b2-metric)). The mathematics of Year 2 is one subject. The Year 3 volume will open the doors deliberately left closed here: Lebesgue integration (discharging the dominated convergence theorem of [Chapter 9](https://one-course.com/books/math/4/en/chapter/9-integration#ch-b2-integration)), measure-theoretic probability on uncountable spaces, and the inverse function theorem’s full proof ([Chapter 15](https://one-course.com/books/math/4/en/chapter/15-differential-calculus#ch-b2-diffcalc)) in the setting of differential geometry.

## 23.5 Exercises

**Exercise 23.1 ★.**

Compute the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) of the uniform [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) on $\{1, 2,
\dots, 6\}$ (a fair die). Show that the sum of two fair dice *cannot* be uniform on $\{2, \dots, 12\}$: factor $G_{X+Y}$ and count roots. *(A uniform sum would force $G_X(t)G_Y(t) =
\frac{t^2}{11}\sum_{k=0}^{10}t^k$, whose nonzero roots are the $11$-th roots of unity other than $1$ — none of them real — while $G_X/t$ and $G_Y/t$ are real polynomials of degree $5$, each owning at least one real root.)*

**Solution of Exercise 23.1.**

Fair die: $G(t) = \frac16(t + t^2 + \dots + t^6) = \frac t6(1 + t
+ \dots + t^5)$. If the sum of two fair dice were uniform on $\{2, \dots, 12\}$, then

$$
G(t)^2 = \frac{t^2}{36}\,h(t)^2
= \frac{t^2}{11}\sum_{k=0}^{10}t^k ,
\qquad h(t) = 1 + t + \dots + t^5 .
$$

Now $h$ is a real polynomial of odd degree $5$, so it has a real root (intermediate value theorem; concretely $h(-1) = 0$), hence $h^2$ has a real root. But $\sum_{k=0}^{10}t^k$ has none: it is positive for $t \geq 0$, and for $t < 0$ it equals $\frac{t^{11} - 1}{t - 1}$, a quotient of two negative numbers. Contradiction — the sum of two fair dice is never uniform (as the familiar triangular [distribution](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of dice sums confirms).

**Exercise 23.2 ★.**

Using [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci), recover $\E$ and $V$ for the binomial and geometric [laws](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) ([Theorem 23.7](#thm-b2-genfun-moments)).

**Solution of Exercise 23.2.**

*Binomial:* $G(t) = (1 - p + pt)^n$, $G'(t) = np(1 - p +
pt)^{n-1}$, $G''(t) = n(n-1)p^2(1 - p + pt)^{n-2}$, so

$$
\E(X) = G'(1) = np,
\qquad
V(X) = G''(1) + G'(1) - G'(1)^2
= n(n-1)p^2 + np - n^2p^2 = np(1-p).
$$

*Geometric* ($q = 1 - p$): $G(t) = \frac{pt}{1 - qt}$, so $G'(t) = \frac{p}{(1 - qt)^2}$ and $G''(t) = \frac{2pq}{(1 -
qt)^3}$; at $t = 1$ (using $1 - q = p$):

$$
\E(X) = \frac{p}{p^2} = \frac1p,
\qquad
V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2}
= \frac{2q + p - 1}{p^2}
= \frac{q}{p^2} ,
$$

matching [Exercise 22.1](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#exo-b2-randomvar-1) with less work.

**Exercise 23.3 ★.**

Two loaded dice: is it possible to load two dice (independently, identically or not) so that their sum is uniform on $\{2, \dots,
12\}$? *(Same factorization obstruction as in [Exercise 23.1](#exo-b2-genfun-1): the answer is no even with different loadings, because each factor $G_X(t)/t$ has odd degree $5$, hence a real root, while the target has none.)*

**Solution of Exercise 23.3.**

No, even with different loadings. Suppose $X, Y$ are [laws](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) on $\{1, \dots, 6\}$ with uniform sum. Then $G_X(t) = t\,a(t)$ and $G_Y(t) = t\,b(t)$ with $a, b$ real polynomials of degree *at most* $5$ — and their degrees must sum to $10$ (the sum reaches $12$ with positive probability), so $\deg a = \deg b = 5$, both odd. As in [Exercise 23.1](#exo-b2-genfun-1),

$$
a(t)\,b(t) = \frac{1}{11}\sum_{k=0}^{10}t^k
$$

would force a real root on the left (each odd-degree real polynomial has one) and none on the right. So no loading of two [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) dice — equal or not — produces a uniform sum.

**Exercise 23.4 ★★.**

Let $X_1, X_2, \dots$ be [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) Bernoulli $\mathcal{B}(p)$ and $N \sim \mathcal{P}(\lambda)$ [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) of them. Show, via [Theorem 23.17](#thm-b2-genfun-compound), that $S = X_1 + \dots + X_N
\sim \mathcal{P}(\lambda p)$: a Poisson number of items, each kept with probability $p$, leaves a Poisson number — *thinning*. Compute also the [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) of the discarded count and admire: it is $\mathcal{P}(\lambda(1-p))$, and one can show it is independent of $S$.

**Solution of Exercise 23.4.**

By [Theorem 23.17](#thm-b2-genfun-compound) with $G_N(s) = e^{\lambda(s-1)}$ and $G_X(t) = 1 - p + pt$:

$$
G_S(t) = e^{\lambda(1 - p + pt - 1)} = e^{\lambda p(t - 1)} :
$$

$S \sim \mathcal{P}(\lambda p)$. The discarded count $D = N - S$ counts the same items kept with probability $1 - p$, so by the same computation $D \sim \mathcal{P}(\lambda(1 - p))$. [Independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence), directly: for $j, k \in \N$,

$$
\begin{align*}
\P(S = j,\ D = k)
&= \P(N = j + k)\,\binom{j+k}{j}p^jq^k
= e^{-\lambda}\frac{\lambda^{j+k}}{(j+k)!}\,
\frac{(j+k)!}{j!\,k!}\,p^jq^k\\
&= \Bigl(e^{-\lambda p}\frac{(\lambda p)^j}{j!}\Bigr)
\Bigl(e^{-\lambda q}\frac{(\lambda q)^k}{k!}\Bigr)
\end{align*}
$$

with $q = 1 - p$: the joint [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) factors as $\mathcal{P}(\lambda p) \otimes \mathcal{P}(\lambda q)$. A Poisson flow split at random yields *[independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence)* Poisson flows — a small miracle constantly used in queueing theory.

**Exercise 23.5 ★★.**

(Negative binomial) Let $T_r$ be the number of tosses to obtain $r$ heads (head probability $p$). Write $T_r$ as a sum of $r$ [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) geometric variables, deduce

$$
G_{T_r}(t) = \Bigl(\frac{pt}{1 - (1-p)t}\Bigr)^{r},
\qquad
\E(T_r) = \frac rp,
\qquad
V(T_r) = \frac{r(1-p)}{p^2},
$$

and expand $G_{T_r}$ to find $\P(T_r = n) = \binom{n-1}{r-1}
p^r(1-p)^{n-r}$.

**Solution of Exercise 23.5.**

The waiting times between consecutive heads are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) geometric $\mathcal{G}(p)$ variables (memorylessness: after each head the game restarts), so $T_r = W_1 + \dots + W_r$ and multiplicativity ([Theorem 23.10](#thm-b2-genfun-product)) gives

$$
G_{T_r}(t) = \Bigl(\frac{pt}{1 - qt}\Bigr)^{r},
\qquad
\E(T_r) = r\,\E(W_1) = \frac rp,
\qquad
V(T_r) = r\,V(W_1) = \frac{rq}{p^2}
$$

($q = 1 - p$; [variances](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-variance) add by [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence)). Expansion: by the generalized binomial series ([Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)), $(1 - qt)^{-r} = \sum_{m\geq0}
\binom{m + r - 1}{r - 1}q^mt^m$, so the coefficient of $t^n$ in $p^rt^r(1 - qt)^{-r}$ is (with $m = n - r$)

$$
\P(T_r = n) = \binom{n-1}{r-1}p^r(1-p)^{n-r},
\qquad n \geq r ,
$$

the *negative binomial* [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) — combinatorially: the $r$-th head falls at toss $n$ iff the previous $r - 1$ heads choose their places among the first $n - 1$ tosses.

**Exercise 23.6 ★★.**

For the offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $p_0 = \frac18$, $p_1 = \frac38$, $p_2 =
\frac38$, $p_3 = \frac18$: compute $m$, decide supercriticality, and compute the extinction probability $q$ exactly. *(Factor out the root $t = 1$ of $G(t) - t$.)*

**Solution of Exercise 23.6.**

$m = 1\cdot\frac38 + 2\cdot\frac38 + 3\cdot\frac18 = \frac{3 + 6 +
3}{8} = \frac32 > 1$: supercritical. The [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) is

$$
G(t) = \frac{1 + 3t + 3t^2 + t^3}{8} = \frac{(1 + t)^3}{8} ,
$$

so fixed points solve $(1 + t)^3 = 8t$, i.e. $t^3 + 3t^2 - 5t + 1
= 0$. Factoring out the guaranteed root $t = 1$:

$$
t^3 + 3t^2 - 5t + 1 = (t - 1)\bigl(t^2 + 4t - 1\bigr),
$$

and $t^2 + 4t - 1 = 0$ gives $t = -2 \pm \sqrt5$. The root in $\intco{0}{1}$ is $\sqrt5 - 2 \approx 0.236$: by [Theorem 23.25](#thm-b2-genfun-extinction),

$$
q = \sqrt 5 - 2 .
$$

(A pleasant check: the offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) is that of $3$ [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) fair coins, $Z_1 \sim \mathcal{B}(3, \frac12)$.)

**Exercise 23.7 ★★★.**

(Total progeny) In a subcritical [branching process](#pb-b2-genfun-1) ($m < 1$), let $Y = \sum_{n\geq0} Z_n$ be the total number of individuals ever born. Show $\E(Y) = \sum_n m^n = \frac{1}{1 - m}$ (justify the exchange of summations), and prove that the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $H = G_Y$ satisfies the functional equation $H(t) = t\,G(H(t))$. *(The ancestor, plus the total progenies of each of its children, which are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) copies of $Y$.)*

**Solution of Exercise 23.7.**

*[Expectation](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation).* First $\E(Z_n) = m^n$: by [Theorem 23.17](#thm-b2-genfun-compound), $\E(Z_{n+1}) = \E(Z_n)\,m$, and $\E(Z_0) = 1$. The family $\bigl(Z_n(\omega)\P(\{\omega\})
\bigr)_{n, \omega}$ is nonnegative, so Fubini for families applies unconditionally:

$$
\E(Y) = \sum_{n=0}^{\infty}\E(Z_n)
= \sum_{n=0}^\infty m^n = \frac{1}{1 - m} < \infty
$$

(in particular $Y$ is almost surely finite: consistent with certain extinction in the subcritical case).

*Functional equation.* Decompose the population by the ancestor’s children: if the ancestor has $Z_1 = k$ children, the total progeny is $Y = 1 + Y_1 + \dots + Y_k$, where $Y_i$ is the total progeny of the $i$-th child’s line — and the $Y_i$ are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) copies of $Y$, independent of $Z_1$ (distinct lines use disjoint, [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) reproduction [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space)). Conditioning on $Z_1$ as in [Theorem 23.17](#thm-b2-genfun-compound):

$$
H(t) = \E\bigl(t^Y\bigr)
= t\sum_{k=0}^\infty \P(Z_1 = k)\,H(t)^k
= t\,G\bigl(H(t)\bigr),
$$

the factor $t$ accounting for the ancestor itself. (For the [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $p_0 = 1 - p$, $p_2 = p$ of binary branching, this quadratic equation in $H$ can be solved explicitly and expanded — the [Catalan numbers](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-catalan) of [Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries) count the family trees.)

**Exercise 23.8 ★★★.**

Let $X$ have [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $G$ with [radius of convergence](https://one-course.com/books/math/4/en/chapter/11-power-series#def-b2-powerseries-radius) $>
1$. Prove the *exponential tail bound*: there are $C > 0$ and $\rho \in \intoo{0}{1}$ with $\P(X \geq n) \leq C\rho^n$. *(Markov applied to $t^X$ for a fixed $t > 1$ inside the disk.)* Conversely, show that if $\P(X \geq n) \leq C\rho^n$ with $\rho < 1$, the radius of $G$ is $\geq 1/\rho > 1$.

**Solution of Exercise 23.8.**

Let $R > 1$ be the radius and fix $t \in \intoo{1}{R}$. Then $\E(t^X) = G(t) < \infty$, and Markov’s inequality ([Theorem 22.15](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#thm-b2-randomvar-markov)) applied to the nonnegative variable $t^X$ at level $t^n$:

$$
\P(X \geq n) = \P\bigl(t^X \geq t^n\bigr)
\leq \frac{G(t)}{t^n} = C\rho^n,
\qquad C = G(t),\quad \rho = \frac1t \in \intoo{0}{1}.
$$

*Converse:* if $\P(X \geq n) \leq C\rho^n$, then $p_n \leq
\P(X \geq n) \leq C\rho^n$, so for $\abs t < \frac1\rho$ the series $\sum p_n\abs t^n$ is dominated by the convergent geometric series $C\sum(\rho\abs t)^n$: the radius is at least $\frac1\rho > 1$. Radius of the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) and geometric decay of the tail are two faces of the same property.

**Exercise 23.9 ★★★.**

([Continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) theorem, elementary case) Let $X, X_1, X_2, \dots$ be $\N$-valued with $G_{X_n}(t) \to G_X(t)$ for every $t \in
\intco{0}{1}$. Show that $\P(X_n = k) \to \P(X = k)$ for every $k$. *(Induction on $k$: for $k = 0$ take $t \to 0$ — carefully: fix $t$ small, use $\abs{\P(X_n = 0) - G_{X_n}(t)}
\leq \frac{t}{1-t}$, valid since the tail $\sum_{j \geq 1}p_jt^j
\leq \frac{t}{1 - t}$; then diagonalize. For the induction step, consider $\frac{G(t) - \P(X = 0)}{t}$, the [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) of a shifted [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law).)*

**Solution of Exercise 23.9.**

Write $p_k^{(n)} = \P(X_n = k)$, $p_k = \P(X = k)$.

*Case $k = 0$.* For $t \in \intoo{0}{1}$ and any [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $(q_j)$ with $\sum_j q_j \leq 1$:

$$
\Bigl|\,q_0 - \sum_j q_jt^j\Bigr|
= \sum_{j \geq 1} q_j t^j
\leq \sum_{j\geq1}t^j = \frac{t}{1 - t} .
$$

Hence

$$
\abs{p_0^{(n)} - p_0}
\leq \frac{2t}{1 - t}
+ \abs{G_{X_n}(t) - G_X(t)} .
$$

Given $\varepsilon > 0$, choose $t$ with $\frac{2t}{1-t} <
\frac\varepsilon2$, then $n_0$ such that the last term is $<
\frac\varepsilon2$ for $n \geq n_0$: so $p_0^{(n)} \to p_0$.

*Induction step.* Assume $p_j^{(n)} \to p_j$ for $j < k$. Consider the *shifted* functions

$$
g_n(t) = \frac{G_{X_n}(t) - p^{(n)}_0}{t}
= \sum_{j\geq0} p^{(n)}_{j+1}t^j,
\qquad
g(t) = \frac{G_X(t) - p_0}{t} ,
$$

[generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) of the sub-probability sequences $(p^{(n)}_{j+1})_j$ (total mass $\leq 1$, which is all the $k = 0$ argument used). For fixed $t \in \intoo{0}{1}$, $g_n(t)
\to g(t)$ by hypothesis and the case $k = 0$. Applying the $k =
0$ argument to $g_n$ gives $p_1^{(n)} \to p_1$; iterating the shift $k$ times gives $p_k^{(n)} \to p_k$ for every $k$. (This is the discrete, elementary instance of Lévy’s [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) theorem, whose general form — for characteristic functions — is a Year 3 landmark.)

**Exercise 23.10 ★.**

(Parity trick) Show that for an $\N$-valued variable $X$,

$$
\P(X \text{ even}) = \frac{1 + G_X(-1)}{2} ,
$$

and compute this probability for $X \sim \mathcal P(\lambda)$ and $X \sim \mathcal B(n, p)$. What does $G_X(-1) \to 0$ mean probabilistically?

**Solution of Exercise 23.10.**

[Pointwise](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def), $\frac{1 + (-1)^X}{2}$ equals $1$ when $X$ is even and $0$ when odd, so taking [expectations](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-expectation) (transfer),

$$
\P(X \text{ even}) = \frac{1 + \E\bigl((-1)^X\bigr)}2 =
\frac{1 + G_X(-1)}2 .
$$

Poisson: $\frac{1 + \eu^{-2\lambda}}2 \to \frac12$ as $\lambda$ grows. Binomial: $\frac{1 + (1 - 2p)^n}2$. In both cases $G_X(-1) \to 0$ says the parity of $X$ becomes a fair coin: the [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) spreads over many integers and forgets its parity.

**Exercise 23.11 ★★.**

(Sicherman dice) Verify the factorization of the fair-die [generating function](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci)

$$
\frac{t + t^2 + \dots + t^6}{6}
= \frac{t\,(1 + t)(1 + t + t^2)(1 - t + t^2)}{6},
$$

and show that the two dice with faces $\{1, 2, 2, 3, 3, 4\}$ and $\{1, 3, 4, 5, 6, 8\}$ have [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) $\frac{t(1+t)(1+t+t^2)}6$ and $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6$, whose product is that of two standard dice: these exotic dice produce every total $2,
\dots, 12$ with exactly the standard probabilities.

**Solution of Exercise 23.11.**

$t + \dots + t^6 = t\,\frac{1 - t^6}{1 - t}$ and $1 - t^6 =
(1 - t)(1 + t)(1 + t + t^2)(1 - t + t^2)$, giving the stated factorization. For the first die, $(1 + t)(1 + t + t^2) = 1 +
2t + 2t^2 + t^3$, so $\frac{t(1+t)(1+t+t^2)}6 = \frac{t +
2t^2 + 2t^3 + t^4}6$: faces $\{1, 2, 2, 3, 3, 4\}$. For the second, expanding

$$
(1 + 2t + 2t^2 + t^3)(1 - t + t^2)^2 = 1 + t^2 + t^3 + t^4 +
t^5 + t^7,
$$

so $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6 = \frac{t + t^3 + t^4
+ t^5 + t^6 + t^8}6$: faces $\{1, 3, 4, 5, 6, 8\}$. The product of the two [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) regroups the six factors into $\bigl(\frac{t(1+t)(1+t+t^2)(1-t+t^2)}6
\bigr)^2$, the square of the standard die’s function: the Sicherman pair has exactly the standard [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) for the total — [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) classify all such regroupings.

**Exercise 23.12 ★★★.**

(Waiting for two heads in a row) A coin with head probability $p$ is tossed until two consecutive heads appear; let $T$ be the number of tosses (the game of [Exercise 21.6](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#exo-b2-proba-6)). Conditioning on the first tosses, derive a linear system for the [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) from the states “no current head” and “one current head”, and conclude

$$
G_T(t) = \frac{p^2t^2}{1 - qt - pqt^2}
\qquad (q = 1 - p);
$$

check $G_T(1) = 1$ and $\E(T) = \dfrac{1 + p}{p^2}$ ($= 6$ for a fair coin).

**Solution of Exercise 23.12.**

Let $A$ and $B$ be the [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci) of the remaining duration started from “no current head” and “one current head”. One toss is spent, then: from state $0$, tails returns to state $0$, heads moves to state $1$; from state $1$, heads ends the game, tails returns to state $0$:

$$
A(t) = t\bigl(q\,A(t) + p\,B(t)\bigr),
\qquad
B(t) = t\bigl(p + q\,A(t)\bigr).
$$

Substituting: $A(1 - qt) = pt\,B = pt(pt + qtA)$, so

$$
G_T(t) = A(t) = \frac{p^2t^2}{1 - qt - pq\,t^2} .
$$

At $t = 1$ the denominator is $1 - q - pq = p(1 - q) = p^2$: $G_T(1) = 1$, the game ends almost surely (as [Exercise 21.6](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#exo-b2-proba-6) showed by recursion). Logarithmic differentiation at $1$: $\E(T) = 2 - \frac{D'(1)}{D(1)}$ with $D(t) = 1 - qt - pqt^2$, $D'(1) = -q - 2pq$:

$$
\E(T) = 2 + \frac{q + 2pq}{p^2} = \frac{2p^2 + q + 2pq}{p^2}
= \frac{1 + p}{p^2},
$$

which is $6$ for $p = \frac12$.

## 23.6 Problem: the Galton–Watson process, solved

**Problem 23.1.**

Weekend problem — growth rates, exact solutions, total progeny, and Kolmogorov’s critical estimate

The extinction criterion ([Theorem 23.25](#thm-b2-genfun-extinction)) splits branching processes into subcritical, critical and supercritical — but it says nothing about *rates*: how fast a doomed line dies, how big a surviving one grows. This problem computes them. We keep the chapter’s notation: offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $(p_k)$ with pgf $G$, mean $m = G'(1)$, generation sizes $Z_n$ ($Z_0 = 1$), iterates $G_n = G_{Z_n}$, extinction probabilities $q_n = \P(Z_n = 0)
\uparrow q$; we always assume $p_1 \neq 1$ and, where second moments appear, $G''(1) < \infty$, and we write $\sigma^2 =
V(Z_1)$.

**Part I — Moments of the generations.**

1. Show $\E(Z_n) = m^n$ *(chain rule on $G_n = G  \circ G_{n-1}$ at $1^-$, using $G_{n-1}(1) = 1$ and [Theorem 23.7](#thm-b2-genfun-moments))* .
2. Establish the recursion $G_n''(1) =  G''(1)\,m^{2(n-1)} + m\,G_{n-1}''(1)$ and solve it: $G_n''(1) = G''(1)\,m^{n-1}\dfrac{m^n - 1}{m - 1}$ for $m \neq 1$ , and $G_n''(1) = n\,G''(1)$ for $m =  1$ .
3. Deduce $$V(Z_n) = \sigma^2m^{n-1}\,\frac{m^n - 1}{m - 1}  \quad (m \neq 1),  \qquad  V(Z_n) = n\,\sigma^2 \quad (m = 1).$$
4. (Subcritical rate, upper bound) For $m < 1$ , show $\P(Z_n > 0) \leq m^n$ *(Markov on the integer-valued $Z_n$)* : extinction is certain with a geometric rate — a quantitative refinement of the chapter’s criterion.
5. (Subcritical rate, lower bound) Using Cauchy–Schwarz on $Z_n\mathbf 1_{Z_n > 0}$, show $$\P(Z_n > 0) \geq \frac{\E(Z_n)^2}{\E(Z_n^2)}  \geq c\,m^{n}  \quad\text{with}\quad  c = \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1} :$$ the geometric rate $m^n$ is exact up to constants.

**Part II — The geometric family, solved exactly.** Let the offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) be geometric on $\N$: $p_k =
qp^k$ ($k \geq 0$), with $0 < p < 1$, $q = 1 - p$.

6. Compute $G(t) = \dfrac{q}{1 - pt}$ and $m = \dfrac  pq$ ; locate the three regimes in terms of $p$ .
7. Solve $G(t) = t$ : show the fixed points are $1$ and $q/p = 1/m$ , and recover the extinction probability $q_{\mathrm{ext}} = \min(1, 1/m)$ .
8. Prove by induction the closed forms $$q_n = \frac{m^n - 1}{m^{n+1} - 1} \quad (m \neq 1),  \qquad  q_n = \frac{n}{n+1} \quad (m = 1).$$
9. Deduce the exact rates: $1 - q_n \sim (1 - m)\,m^n$ in the subcritical case, and $q_{\mathrm{ext}} - q_n  \sim \dfrac{m - 1}{m^{2}}\cdot m^{-n}$ in the supercritical case; check that the supercritical contraction ratio is $G'(q_{\mathrm{ext}}) = 1/m$ .
10. Critical case ( $p = \tfrac12$ ): compute $\sigma^2 =  2$ and note $1 - q_n = \frac1{n+1}$ : survival decays like $\frac1n$ — neither geometric nor [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) .
11. Still critical: prove by induction the full iterate $$G_n(t) = \frac{n - (n-1)t}{n + 1 - nt},$$ and deduce that conditioned on survival, $Z_n$ is geometric on $\N^*$ with parameter $\frac1{n+1}$: $$\P(Z_n = k \mid Z_n > 0) = \frac1{n+1}  \Bigl(\frac{n}{n+1}\Bigr)^{k-1},  \qquad  \E(Z_n \mid Z_n > 0) = n + 1 .$$ The average line dies, but the surviving lines have size of order $n$.

**Part III — Total progeny.** Let $Y =
\sum_{n\geq0}Z_n \in \N^* \cup \{\infty\}$ be the total number of individuals ever born, and $H(t) =
\sum_{k\geq1}\P(Y = k)t^k$.

12. Justify $\P(Y < \infty) = q_{\mathrm{ext}}$ , and recall from [Exercise 23.7](#exo-b2-genfun-7) the functional equation $H(t) = t\,G(H(t))$ (whose derivation did not use $m < 1$ ).
13. (Binary branching) For $p_0 = p_2 = \frac12$ (critical), solve the functional equation: $$H(t) = \frac{1 - \sqrt{1 - t^2}}{t},$$ and expand with [Example 11.21](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-catalan) to get $$\P(Y = 2k + 1) = \frac{C_k}{2^{2k+1}},  \qquad C_k = \frac1{k+1}\binom{2k}k ;$$ check the values $\P(Y = 1) = \frac12$ and $\P(Y = 3)  = \frac18$ by direct counting.
14. Differentiating the functional equation at $1^-$ , show that $\E(Y) = \frac{1}{1-m}$ for $m < 1$ , while criticality forces $\E(Y) = \infty$ : the critical total progeny is finite almost surely with infinite mean.
15. With the central binomial asymptotics ([Example 6.14](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ex-b2-comparison-centralbinomial)), show $$\P(Y = 2k+1) \sim \frac{1}{2\sqrt\pi\,k^{3/2}},$$ a heavy $k^{-3/2}$ tail, and deduce $\P(Y > n)  \asymp n^{-1/2}$ (upper and lower bounds of this order suffice).
16. Compare with the fair [random walk](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#pb-b2-proba-1) (the weekend problem of [Chapter 21](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#ch-b2-proba) ): certain but infinite-mean return times there, certain but infinite-mean total progeny here, both with $n^{-3/2}$ local laws. One paragraph on why criticality produces this signature.

**Part IV — Kolmogorov’s estimate at criticality.** Assume $m = 1$, $0 < \sigma^2 = G''(1) <
\infty$.

17. Show that $G''$ extends [continuously](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) to $\intcc01$ *(nonnegative increasing with finite limit)* and deduce the Taylor expansion at $1$: $$G(t) = t + b\,(1-t)^2 + o\bigl((1-t)^2\bigr),  \qquad b = \frac{G''(1)}2 = \frac{\sigma^2}2 .$$
18. For $t \in \intco01$, set $h(t) = \dfrac1{1 - G(t)} -  \dfrac1{1 - t}$. Show $$h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)}  \xrightarrow[t\to1^-]{} b .$$
19. Telescope along the iteration $q_{j+1} = G(q_j)$: $$\frac1{1 - q_n} = 1 + \sum_{j=0}^{n-1}h(q_j),$$ and conclude with a Cesaro argument that $$\P(Z_n > 0) = 1 - q_n \sim \frac{2}{\sigma^2\,n}$$ — *Kolmogorov’s estimate*: every critical [branching process](#pb-b2-genfun-1) dies at the universal rate $1/n$, with only the constant remembering the offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law).
20. Check the estimate against the critical geometric case of question 10.
21. Deduce $\E(Z_n \mid Z_n > 0) = \dfrac{1}{1 - q_n}  \sim \dfrac{\sigma^2 n}{2}$ *(note $\E(Z_n  \mathbf 1_{Z_n>0}) = \E(Z_n) = 1$)* , and check it against question 11: conditioned on survival, the population grows *linearly* — the critical tightrope between death and explosion.

**Part V — Applications and synthesis.**

22. (Epidemics, chain reactions) For a Poisson offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $\mathcal P(\lambda)$ — each case infects $\mathcal P(\lambda)$ new cases — write the extinction equation $q = \eu^{\lambda(q-1)}$ and solve it numerically for $\lambda = 1.5$ ( $q \approx  0.417$ ) and $\lambda = 2$ ( $q \approx 0.203$ ): starting from one case, a major outbreak is *not* certain even when $\lambda > 1$ . Explain why the iteration $q_{n+1} = \eu^{\lambda(q_n - 1)}$ from $q_0 = 0$ converges to the right root.
23. Starting from $k$ ancestors instead of one, show that the extinction probability is $q^k$ . Application: with $\lambda = 1.5$ , how many initial cases make an outbreak at least $99\%$ likely?
24. (Conditioning a supercritical process on extinction) For $m > 1$ with extinction probability $q \in  \intoo01$ : first prove by convexity that $G'(q) < 1$ at the smallest fixed point, and deduce $q_{\mathrm{ext}} - q_n = O\bigl(G'(q)^n\bigr)$ (geometric convergence, as question 9 exemplified). Then show that $\widehat G(t) = G(qt)/q$ is the pgf of a bona fide offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) , with mean $\widehat m =  G'(q) < 1$ : a subcritical companion process. Verify on the geometric family: conditioning the supercritical $(p, q)$ -process on extinction swaps $p$ and $q$ . (The full statement — the conditioned process *is* the companion process — is proved in the Year 3 volume; here you have verified its generating-function shadow.)
25. Synthesis: draw up the trichotomy table — for $m <  1$ , $m = 1$ , $m > 1$ : value of $q$ ; rate of $\P(Z_n >  0)$ or of $q - q_n$ ; $\E(Y)$ ; size of a surviving generation. State in one sentence per tool how composition of pgfs, convexity, Taylor at $1^-$ , and Cesaro averaging carried the whole problem, and what the Year 3 volume adds (the martingale $Z_n/m^n$ and Yaglom’s exponential limit [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) ).

**Solution of Problem 23.1.**

**1.** For $t \in \intoo01$, the chain rule on $G_n = G
\circ G_{n-1}$ gives $G_n'(t) =
G'\bigl(G_{n-1}(t)\bigr)G_{n-1}'(t)$. As $t \to 1^-$, $G_{n-1}(t) \uparrow 1$, and $G'$ is nondecreasing with left limit $m$ at $1$, so the first factor tends to $m$; by induction the second tends to $m^{n-1}$. By [Theorem 23.7](#thm-b2-genfun-moments), $\E(Z_n) = G_n'(1^-) = m^n$.

**2.** Differentiating once more,

$$
G_n'' = G''(G_{n-1})\,(G_{n-1}')^2 +
G'(G_{n-1})\,G_{n-1}'',
$$

and letting $t \to 1^-$: $a_n = G''(1)m^{2(n-1)} + m\,
a_{n-1}$ with $a_n = G_n''(1)$, $a_1 = G''(1)$. For $m \neq
1$ one checks by induction that $a_n = G''(1)\,m^{n-1}
\frac{m^n - 1}{m - 1}$ (the recursion adds $G''(1)m^{2n-2}$ to $m\cdot G''(1)m^{n-2}\frac{m^{n-1}-1}{m-1}$, and $m^{n-1} + \frac{m^{n-1}-1}{m-1} = \frac{m^n - 1}{m-1}$); for $m = 1$, $a_n = a_{n-1} + G''(1) = n\,G''(1)$.

**3.** $V(Z_n) = a_n + m^n - m^{2n}$ and $G''(1) =
\sigma^2 + m^2 - m$. For $m \neq 1$, the piece $(m^2 -
m)m^{n-1}\frac{m^n-1}{m-1} = m^n(m^n - 1)$ cancels $m^n -
m^{2n}$ exactly, leaving $V(Z_n) =
\sigma^2m^{n-1}\frac{m^n-1}{m-1}$. For $m = 1$: $V(Z_n) =
nG''(1) = n\sigma^2$.

**4.** $Z_n$ is a nonnegative integer variable, so $\P(Z_n > 0) = \P(Z_n \geq 1) \leq \E(Z_n) = m^n$ by Markov ([Theorem 22.15](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#thm-b2-randomvar-markov)). For $m < 1$ this decays geometrically — and [summably](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable), so Borel–Cantelli even gives that only finitely many generations are nonempty, which is extinction again.

**5.** Cauchy–Schwarz: $\E(Z_n)^2 = \E(Z_n\mathbf
1_{Z_n>0})^2 \leq \E(Z_n^2)\,\P(Z_n > 0)$. With question 3 and $m < 1$:

$$
\E(Z_n^2) = V(Z_n) + m^{2n}
\leq \frac{\sigma^2m^{n-1}}{1-m} + m^{2n},
$$

so, dividing $m^{2n}$ by this bound and simplifying by $m^n$,

$$
\P(Z_n > 0) \geq \frac{m^n}{\frac{\sigma^2}{m(1-m)} + m^n}
\geq \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1}m^n ,
$$

using $m^n \leq 1$ in the denominator. With question 4: $\P(Z_n > 0) \asymp m^n$.

**6.** $G(t) = q\sum_k(pt)^k = \frac{q}{1 - pt}$, and $m
= G'(1) = \frac{pq}{(1-p)^2} = \frac pq$. Subcritical for $p
< \frac12$, critical for $p = \frac12$, supercritical for $p
> \frac12$.

**7.** $G(t) = t$ reads $pt^2 - t + q = 0$, with roots $\frac{1 \pm \abs{p - q}}{2p}$, i.e. $1$ and $\frac qp =
\frac1m$. The extinction probability is the smallest fixed point in $\intcc01$ ([Theorem 23.25](#thm-b2-genfun-extinction)): $q_{\mathrm{ext}} = 1$ if $m \leq 1$, and $\frac1m$ if $m >
1$.

**8.** For $m \neq 1$, with $p = \frac m{m+1}$, $q =
\frac1{m+1}$: if $q_n = \frac{m^n - 1}{m^{n+1} - 1}$, then

$$
1 - p\,q_n = \frac{(m+1)(m^{n+1} - 1) - m(m^n - 1)}
{(m+1)(m^{n+1} - 1)} = \frac{m^{n+2} - 1}{(m+1)(m^{n+1} -
1)},
$$

so $q_{n+1} = \frac{q}{1 - pq_n} = \frac{m^{n+1} -
1}{m^{n+2} - 1}$; the base case $q_0 = 0$ holds. For $m = 1$: $G(t) = \frac1{2 - t}$ and $q_{n+1} = \frac1{2 -
\frac{n}{n+1}} = \frac{n+1}{n+2}$, with $q_0 = 0$.

**9.** $1 - q_n = \frac{m^n(m - 1)}{m^{n+1} - 1}$. For $m < 1$ the denominator tends to $-1$: $1 - q_n \sim (1 -
m)\,m^n$. For $m > 1$:

$$
q_{\mathrm{ext}} - q_n = \frac1m - \frac{m^n - 1}{m^{n+1} -
1} = \frac{m - 1}{m\,(m^{n+1} - 1)} \sim \frac{m -
1}{m^{2}}\;m^{-n} .
$$

And $G'(t) = \frac{pq}{(1 - pt)^2}$ evaluated at $t = \frac
qp$ (where $1 - pt = 1 - q = p$) gives $G'(q_{\mathrm{ext}})
= \frac qp = \frac1m$: the observed ratio $m^{-1}$ is exactly the derivative at the attracting fixed point.

**10.** For $p = \frac12$: $G''(t) = \frac{1/4}{(1 -
t/2)^3}$, so $G''(1) = 2$ and $\sigma^2 = G''(1) + m - m^2 =
2$. The closed form gives $1 - q_n = \frac1{n+1}$: the survival probability decays like $1/n$ — too slowly to be [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable), unlike any subcritical rate.

**11.** Induction: $G_1(t) = \frac1{2-t}$ matches the formula for $n = 1$, and

$$
G(G_n(t)) = \cfrac{1}{2 - \cfrac{n - (n-1)t}{n+1 - nt}}
= \frac{n + 1 - nt}{2(n+1) - 2nt - n + (n-1)t}
= \frac{n+1 - nt}{n + 2 - (n+1)t} .
$$

Then

$$
\frac{G_n(t) - q_n}{1 - q_n}
= (n+1)\,\Bigl(\frac{n - (n-1)t}{n+1 - nt} -
\frac{n}{n+1}\Bigr)
= \frac{t}{n + 1 - nt}
= \frac{\frac{t}{n+1}}{1 - \frac{n}{n+1}t} ,
$$

the pgf of the geometric [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) $\mathcal G\bigl(\frac1{n+1}
\bigr)$ on $\N^*$ ([Example 23.4](#ex-b2-genfun-classical)): given survival, $\P(Z_n = k \mid Z_n > 0) =
\frac1{n+1}\bigl(\frac n{n+1}\bigr)^{k-1}$, with conditional mean $n + 1$. The unconditional mean $1 = \E(Z_n)$ is the product of a vanishing survival probability and a linearly growing conditional size.

**12.** If the line goes extinct at generation $n$, then $Y = Z_0 + \dots + Z_{n-1}$ is finite; if it never goes extinct, $Y \geq \sum_n 1 = \infty$. So $\{Y < \infty\}$ is the extinction [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) and $\P(Y < \infty) = q_{\mathrm{ext}}$. The derivation of $H(t) = tG(H(t))$ in [Exercise 23.7](#exo-b2-genfun-7) — the ancestor contributes the factor $t$, its children found [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) copies of $Y$ counted through $G$ — used only [Theorem 23.17](#thm-b2-genfun-compound), valid in every regime.

**13.** With $G(s) = \frac{1 + s^2}2$ the equation reads $tH^2 - 2H + t = 0$, so $H = \frac{1 - \sqrt{1 - t^2}}{t}$ (the root with $H(0) = 0$). Comparing with the Catalan series $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ ([Example 11.21](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-catalan)): $H(t) = \frac
t2\,C\bigl(\frac{t^2}4\bigr) =
\sum_{k\geq0}C_k\,\frac{t^{2k+1}}{2^{2k+1}}$, i.e. $\P(Y =
2k+1) = C_k2^{-2k-1}$. Checks: $\P(Y = 1) = C_0/2 = \frac12$ (the ancestor has no child); $\P(Y = 3) = C_1/8 = \frac18$ (two children, both childless: $\frac12\cdot\frac12\cdot
\frac12$).

**14.** Differentiating $H = tG(H)$ on $\intoo01$ and letting $t \to 1^-$ (monotone limits as in [Theorem 23.7](#thm-b2-genfun-moments)): $H'(1)\bigl(1 - G'(H(1))\bigr)
= G(H(1))$. In the subcritical case $H(1) = 1$ and $\E(Y) =
H'(1) = \frac1{1 - m}$. In the critical case $G'(1) = 1$ makes the left factor vanish while the right side is $1$: no finite $H'(1)$ can exist, so $\E(Y) = \infty$ — yet $\P(Y <
\infty) = q = 1$.

**15.** $C_k = \frac1{k+1}\binom{2k}k \sim
\frac{4^k}{\sqrt\pi\,k^{3/2}}$ by [Example 6.14](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ex-b2-comparison-centralbinomial), so

$$
\P(Y = 2k+1) = \frac{C_k}{2\cdot4^{k}} \sim
\frac1{2\sqrt\pi\,k^{3/2}} .
$$

Summing the tail (comparison with $\int_K^\infty
k^{-3/2}\dd k = 2K^{-1/2}$, above and below): $\P(Y > 2K)
\asymp K^{-1/2}$, i.e. $\P(Y > n) \asymp n^{-1/2}$ — a heavy tail with infinite mean, quantifying question 14.

**16.** Both critical objects — the fair walk’s return time (the weekend problem of [Chapter 21](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#ch-b2-proba)) and the critical total progeny — are almost surely finite with infinite mean, with local laws of exponent $-3/2$ and tails of exponent $-1/2$. This is no coincidence: exploring a family tree child by child produces a $\pm1$ path (one step up per birth, one down per death) which is exactly a fair walk, and $Y$ becomes a first passage time. Criticality means zero drift: the process is always on the verge of both extinction and explosion, and the $\sqrt{}$-scale fluctuations of zero-drift randomness produce precisely these exponents.

**17.** $G''(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ has nonnegative terms, so it is nondecreasing on $\intco01$ with finite limit $G''(1) = \sigma^2$ (criticality makes $\E Z_1(Z_1 - 1) = \sigma^2$); a nondecreasing function with limit equal to the boundary value is [continuous](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) at $1$. Taylor with integral remainder at the point $1$:

$$
G(t) = 1 + (t - 1) + \int_1^t(t - s)G''(s)\,\dd s
= t + \frac{G''(1)}2(1-t)^2 + o\bigl((1-t)^2\bigr),
$$

since $G''(s) = G''(1) + o(1)$ as $s \to 1^-$.

**18.** Reducing to a common denominator, $h(t) =
\frac{G(t) - t}{(1 - G(t))(1 - t)}$. By question 17 the numerator is $b(1-t)^2 + o((1-t)^2)$ and $1 - G(t) = (1 -
t)\bigl(1 - b(1-t) + o(1-t)\bigr)$, so $h(t) \to b$.

**19.** By definition of $h$ at $t = q_j$ and $G(q_j) =
q_{j+1}$: $\frac1{1 - q_{j+1}} - \frac1{1-q_j} = h(q_j)$; summing from $j = 0$ ($q_0 = 0$) gives the display. Since the critical process dies out, $q_j \uparrow 1$, so $h(q_j) \to
b$ and the Cesaro mean $\frac1n\sum_{j<n}h(q_j) \to b$: $\frac1{1-q_n} \sim bn$, i.e.

$$
\P(Z_n > 0) \sim \frac1{bn} = \frac{2}{\sigma^2 n} .
$$

**20.** Geometric critical case: $\sigma^2 = 2$ (question 10), so Kolmogorov predicts $1 - q_n \sim \frac1n$ — and the exact value is $\frac1{n+1}$.

**21.** Since $Z_n\mathbf 1_{Z_n > 0} = Z_n$, $\E(Z_n
\mid Z_n > 0) = \frac{\E(Z_n)}{\P(Z_n > 0)} = \frac1{1 -
q_n} \sim \frac{\sigma^2n}2$. In the geometric case this is $n + 1$, matching question 11 exactly ($\sigma^2 = 2$). The critical picture: extinction is certain, the mean size is frozen at $1$, and the rare surviving lines have size growing linearly — each factor balancing the other.

**22.** For $\mathcal P(\lambda)$ offspring, $G(t) =
\eu^{\lambda(t-1)}$ and the extinction probability is the smallest root of $q = \eu^{\lambda(q-1)}$. Numerically: $\lambda = 1.5$ gives $q \approx 0.417$ (iterate $q \mapsto
\eu^{1.5(q-1)}$: $0, 0.223, 0.312, 0.356, \dots \to 0.4172$); $\lambda = 2$ gives $q \approx 0.203$. So one index case sparks a major outbreak with probability $58\%$ ($\lambda = 1.5$) or $80\%$ ($\lambda = 2$) — likely, not certain. The iteration from $q_0 = 0$ converges to the *smallest* root because $G$ is nondecreasing: by induction $q_n \leq r$ for any fixed point $r$, and $(q_n)$ increases (it is $\P(Z_n = 0)$), so its limit is a fixed point below all others.

**23.** The $k$ ancestors found [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) family trees, and total extinction is the intersection of $k$ [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) extinction [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space): probability $q^k$. For $\lambda = 1.5$: outbreak probability $1 - q^k \geq 0.99$ requires $q^k \leq 0.01$, i.e. $k \geq
\frac{\ln 0.01}{\ln 0.417} \approx 5.3$: six initial cases make the outbreak $99\%$ certain.

**24.** *$G'(q) < 1$:* $G - \mathrm{id}$ is [convex](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-convex) and vanishes at $q$ and $1$, so it is $\leq 0$ on $\intcc
q1$; if $G'(q) = 1$, the tangent at $q$ (which convexity places below $G$) would force $G(t) \geq t$ on $\intcc q1$, hence $G \equiv \mathrm{id}$ there, killing all coefficients $p_n$ ($n \geq 2$) and contradicting $m > 1$. *Geometric convergence:* $q_n < q$ for all $n$ (induction, $G$ increasing), and the mean value theorem gives $q - q_{n+1} =
G'(c_n)(q - q_n)$ with $c_n \in \intoo{q_n}q$, so $G'(c_n)
\leq G'(q) < 1$ and $q - q_n \leq q\,G'(q)^n$. *Companion process:* $\widehat G(t) = G(qt)/q =
\sum_kp_kq^{k-1}t^k$ has nonnegative coefficients and $\widehat G(1) = G(q)/q = 1$: a pgf; its mean is $\widehat
G'(1) = G'(q) < 1$: subcritical. Geometric family: $G(t) =
\frac{q}{1-pt}$, $q_{\mathrm{ext}} = \frac qp$, and

$$
\widehat G(t) = \frac pq\cdot\frac{q}{1 - p\frac qp t}
= \frac{p}{1 - qt} :
$$

the geometric offspring [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) with $p$ and $q$ exchanged — the supercritical process seen on its extinction [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) is the mirror subcritical one.

**25.** The table: $m < 1$: $q = 1$, $\P(Z_n > 0)
\asymp m^n$ (questions 4–5), $\E(Y) = \frac1{1-m}$, surviving generations of bounded conditional mean. $m = 1$: $q = 1$, $\P(Z_n > 0) \sim \frac2{\sigma^2n}$ (Kolmogorov), $\E(Y) = \infty$ with $\P(Y > n) \asymp n^{-1/2}$, survivors of size $\sim \frac{\sigma^2n}2$. $m > 1$: $q < 1$ is the smallest fixed point, $q - q_n = O(G'(q)^n)$, $\E(Z_n) = m^n$ growth, and conditioned on dying the process is the subcritical companion (question 24). The tools: composition of pgfs turned population recursion into function iteration; convexity fixed the geometry of the fixed points; Taylor at $1^-$ converted moment hypotheses into local expansions; and Cesaro averaging extracted Kolmogorov’s $1/n$ from a telescoping sum. The Year 3 volume adds the martingale $Z_n/
m^n$ — whose almost-sure limit refines $\E(Z_n) = m^n$ into a trajectory-by-trajectory growth rate — and Yaglom’s theorem, the limit [law](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#def-b2-randomvar-law) behind the conditional geometry observed in question 11.