Ferkans — Interactive Telecom Tutor

From Sums to Compositions

The PGF product rule handles sums of a fixed number of independent RVs. But what if the number of summands is itself random? This arises naturally: the total number of packets in a burst is a random sum of individual packet sizes; the total load on a server is the sum of a random number of jobs.

The compounding theorem says that the PGF of a random sum is a composition of PGFs: $G_S(s) = G_N(G_X(s))$ . This simple formula has far-reaching consequences, including the complete analysis of Galton-Watson branching processes.

Theorem: The Compounding Theorem (Random Sums)

Let $X_1, X_2, \ldots$ be i.i.d. nonneg. integer-valued RVs with common PGF $G_X(s)$ , and let $N$ be a nonneg. integer-valued RV independent of the $X_i$ 's with PGF $G_N(s)$ . Then the random sum

$S = \sum_{i=1}^{N} X_i$

has PGF

$G_S(s) = G_N(G_X(s)).$

Condition on $N = n$ : given $N = n$ , $S$ is a fixed sum of $n$ i.i.d. RVs, so $\mathbb{E}[s^S | N = n] = [G_X(s)]^n$ . Average over $N$ : $G_S(s) = \sum_n [G_X(s)]^n\,p_N[n] = G_N(G_X(s))$ .

Proof

Condition on $N$

$G_S(s) = \mathbb{E}[s^S] = \mathbb{E}[\mathbb{E}[s^S | N]] = \sum_{n=0}^{\infty} \mathbb{E}[s^{X_1 + \cdots + X_n}] \,\mathbb{P}(N = n)$ .

Use independence of $X_i$'s

$\mathbb{E}[s^{X_1 + \cdots + X_n}] = [G_X(s)]^n$ .

Recognize the outer PGF

$G_S(s) = \sum_{n=0}^{\infty} [G_X(s)]^n\,p_N[n] = G_N(G_X(s))$ .

Example: Compound Poisson: Eggs and Chicks

A hen lays $N \sim \text{Poi}(\lambda)$ eggs. Each egg hatches independently with probability $p$ (Bernoulli). How many chicks $K$ does she produce?

Solution

Set up the random sum

$K = \sum_{i=1}^{N} X_i$ where $X_i \sim \text{Bernoulli}(p)$ independent of $N$ .

Apply the compounding theorem

$G_K(s) = G_N(G_X(s)) = e^{(G_X(s) - 1)\lambda} = e^{(1-p+ps - 1)\lambda} = e^{p\lambda(s-1)}$ .

Identify the distribution

$G_K(s) = e^{p\lambda(s-1)}$ is the PGF of $\text{Poi}(p\lambda)$ . Therefore $K \sim \text{Poi}(p\lambda)$ .

This is the Poisson thinning property: independently retaining each event with probability $p$ gives a Poisson process with thinned rate $p\lambda$ .

Definition:
Galton-Watson Branching Process

A Galton-Watson branching process $\{Z_n : n = 0, 1, 2, \ldots\}$ evolves as follows:

$Z_0 = 1$ (start with one individual).
Each individual in generation $n$ independently produces a random number of offspring with common PMF $p$ and PGF $G(s)$ .
$Z_{n+1} = \sum_{i=1}^{Z_n} Y_i$ where $Y_i$ are i.i.d. with PGF $G$ .

The mean offspring number is $\mu = G'(1) = \mathbb{E}[Z_1]$ and the variance is $\sigma^2 = G''(1) + G'(1) - [G'(1)]^2$ .

,

Theorem: PGF of the $n$ -th Generation

The PGF of the population size at generation $n$ is the $n$ -fold composition:

$G_n(s) = G_{Z_n}(s) = \underbrace{G(G(\cdots G(s)\cdots))}_{n\text{ times}} = G^{\circ n}(s).$

Moreover, $G_{n+m}(s) = G_m(G_n(s)) = G_n(G_m(s))$ .

Proof

Induction via compounding

Base case: $G_1(s) = G(s)$ .

Inductive step: $Z_{n+1} = \sum_{i=1}^{Z_n} Y_i$ where the $Y_i$ are i.i.d. with PGF $G$ , independent of $Z_n$ . By the compounding theorem: $G_{n+1}(s) = G_{Z_n}(G(s)) = G_n(G(s))$ .

Since $G_1 = G$ : $G_2(s) = G(G(s)) = G^{\circ 2}(s)$ , and by induction $G_n(s) = G^{\circ n}(s)$ .

Theorem: Moments of the Branching Process

$\mathbb{E}[Z_n] = \mu^n, \qquad \text{Var}(Z_n) = \begin{cases} n\sigma^2 & \text{if } \mu = 1, \\ \frac{\sigma^2(\mu^n - 1)\mu^{n-1}}{\mu - 1} & \text{if } \mu \neq 1. \end{cases}$ $

Proof

Mean

Differentiate $G_n(s) = G(G_{n-1}(s))$ at $s = 1$ : $G_n'(1) = G'(1) \cdot G_{n-1}'(1) = \mu \cdot G_{n-1}'(1)$ . By induction, $\mathbb{E}[Z_n] = G_n'(1) = \mu^n$ .

Variance

Use the law of total variance: $\text{Var}(Z_{n+1}) = \mathbb{E}[\text{Var}(Z_{n+1}|Z_n)] + \text{Var}(\mathbb{E}[Z_{n+1}|Z_n])$ .

Given $Z_n$ , $Z_{n+1}$ is a sum of $Z_n$ i.i.d. RVs, so $\text{Var}(Z_{n+1}|Z_n) = Z_n\sigma^2$ and $\mathbb{E}[Z_{n+1}|Z_n] = Z_n\mu$ .

Thus $\text{Var}(Z_{n+1}) = \sigma^2\mu^n + \mu^2\text{Var}(Z_n)$ . Solving the recurrence with $\text{Var}(Z_0) = 0$ gives the result.

Theorem: Extinction Probability of a Branching Process

The probability of ultimate extinction

$\eta = \lim_{n \to \infty}\mathbb{P}(Z_n = 0) = \lim_{n \to \infty} G_n(0)$

is the smallest non-negative solution of $s = G(s)$ .

If $\mu \leq 1$ (and $\sigma^2 > 0$ ): $\eta = 1$ (certain extinction).
If $\mu > 1$ : $\eta < 1$ (survival with positive probability $1-\eta$ ).

Extinction occurs when the population hits zero — an absorbing state. The fixed-point equation $\eta = G(\eta)$ arises because the process either dies in generation $1$ with probability $G(0)$ , or reaches some generation- $1$ size and then each sub-tree independently faces the same extinction question.

Proof

Monotone convergence of $G_n(0)$

$\mathbb{P}(Z_n = 0) = G_n(0)$ . Since $\{Z_n = 0\} \subseteq \{Z_{n+1} = 0\}$ , the events are nested, so $G_n(0) \uparrow \eta$ .

Fixed-point equation

$G_{n+1}(0) = G(G_n(0))$ . By continuity of $G$ and the limit: $\eta = G(\eta)$ .

Smallest fixed point

If $\psi \geq 0$ satisfies $G(\psi) = \psi$ , then by induction $G_n(0) \leq \psi$ for all $n$ (since $G$ is non-decreasing on $[0,1]$ ), so $\eta \leq \psi$ .

Convexity argument

$G(s)$ is convex on $[0,1]$ (since $G''(s) \geq 0$ ), $G(1) = 1$ , and $G'(1) = \mu$ . If $\mu > 1$ , the tangent line at $s = 1$ has slope $> 1$ , so $G(s) < s$ for $s$ slightly less than $1$ , giving a second fixed point $\eta < 1$ . If $\mu \leq 1$ , the only fixed point on $[0,1]$ is $s = 1$ .

,

Branching Process: PGF Fixed Points and Extinction

Explore the Galton-Watson branching process. The plot shows $y = G(s)$ and $y = s$ . The extinction probability $\eta$ is the smallest intersection point. Adjust the offspring distribution to see how $\mu = G'(1)$ determines whether extinction is certain ( $\mu \leq 1$ ) or not ( $\mu > 1$ ).

Parameters

p_0 = \mathbb{P}(0\text{ offspring})

0.3

p_1 = \mathbb{P}(1\text{ offspring})

0.3

p_2 = \mathbb{P}(2\text{ offspring})

0.4

Example: Geometric Offspring Distribution

Suppose the offspring distribution is geometric: $p[k] = (1-p)p^k$ for $k = 0, 1, 2, \ldots$ with PGF $G(s) = (1-p)/(1-ps)$ . Find the extinction probability.

Solution

Compute the mean

$\mu = G'(1) = p/(1-p)$ . So $\mu \leq 1$ iff $p \leq 1/2$ .

Solve $s = G(s)$

$s = \frac{1-p}{1-ps}$ gives $s(1-ps) = 1-p$ , i.e., $ps^2 - s + (1-p) = 0$ .

Solutions: $s = 1$ and $s = (1-p)/p$ .

Identify the extinction probability

For $p > 1/2$ ( $\mu > 1$ ): $\eta = (1-p)/p < 1$ .

For $p \leq 1/2$ ( $\mu \leq 1$ ): $\eta = 1$ (certain extinction).

For example, with $p = 2/3$ : $\mu = 2$ , $\eta = 1/2$ .

🎓CommIT Contribution(2001)

Branching Process Analysis of Random Access Protocols

G. Caire, D. Tuninetti — IEEE Transactions on Information Theory

The Galton-Watson branching process has direct applications to the analysis of tree-splitting random access protocols (ALOHA variants). When a collision occurs, each colliding user independently retransmits with probability $p$ , creating a branching structure. The stability condition — whether the backlog grows unboundedly — corresponds precisely to the subcritical condition $\mu < 1$ . Caire and Tuninetti analyzed the throughput of coded random access using similar branching arguments, connecting the extinction probability to the packet loss rate.

random-accessbranching-processesthroughput-analysisView Paper →

Historical Note: Galton, Watson, and the Problem of Family Names

19th-20th century

In 1874, Francis Galton posed a question to the readers of the Educational Times: what is the probability that a family name eventually goes extinct? Galton was motivated by observing that many once-prominent English surnames had disappeared. Reverend Henry Watson responded with the generating function analysis — essentially the theory developed in this section.

The irony is that Watson's original solution contained an error: he concluded that extinction was certain regardless of the mean offspring number. The correct result — that survival is possible when $\mu > 1$ — was established by Steffensen (1930) and later clarified by Harris (1963).

Waring's Theorem and Inclusion-Exclusion

The PGF also enables elegant combinatorial results. Waring's theorem provides a formula for $\mathbb{P}(X = k)$ where $X$ counts the number of events from $A_1, \ldots, A_n$ that occur:

$\mathbb{P}(X = k) = \sum_{m=k}^{n} (-1)^{m-k}\binom{m}{k}S_m,$

where $S_m = \sum_{i_1 < \cdots < i_m}\mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_m})$ . The proof is a direct consequence of the relation $G_X(s) = G_S(s-1)$ between the PGF of $X$ and the generating function of the $S_m$ sequence. This is the probabilistic generalization of inclusion-exclusion.

Quick Check

In a Galton-Watson branching process, the offspring PGF satisfies $G(s) = 0.2 + 0.5s + 0.3s^2$ . What is the mean offspring number $\mu$ , and will the process go extinct with probability $1$ ?

$\mu = 1.1$ , extinction probability $< 1$

$\mu = 1.1$ , extinction probability $= 1$

$\mu = 0.8$ , extinction probability $= 1$

$\mu = 1.0$ , extinction probability $= 1$

Correction:

\mu = 1.1

, extinction probability

< 1

$\mu = G'(1) = 0.5 + 2(0.3) = 1.1 > 1$ . Since $\mu > 1$ , the process is supercritical, so $\eta < 1$ — survival occurs with positive probability.

Galton-Watson Branching Process

A stochastic process $\{Z_n\}$ where each individual independently produces offspring with a common distribution. $Z_0 = 1$ , $Z_{n+1} = \sum_{i=1}^{Z_n} Y_i$ . The PGF of $Z_n$ is $G^{\circ n}(s)$ .

Compound Distribution

The distribution of $S = \sum_{i=1}^N X_i$ where $N$ is random and independent of the i.i.d. $X_i$ 's. Its PGF is $G_S(s) = G_N(G_X(s))$ .

Branching Processes and Compound Distributions

From Sums to Compositions

Theorem: The Compounding Theorem (Random Sums)

Condition on $N$

Use independence of $X_i$'s

Recognize the outer PGF

Example: Compound Poisson: Eggs and Chicks

Set up the random sum

Apply the compounding theorem

Identify the distribution

Definition: Galton-Watson Branching Process

Theorem: PGF of the nnn-th Generation

Induction via compounding

Theorem: Moments of the Branching Process

Mean

Variance

Theorem: Extinction Probability of a Branching Process

Monotone convergence of $G_n(0)$

Fixed-point equation

Smallest fixed point

Convexity argument

Branching Process: PGF Fixed Points and Extinction

Parameters

Example: Geometric Offspring Distribution

Compute the mean

Solve $s = G(s)$

Identify the extinction probability

Branching Process Analysis of Random Access Protocols

Historical Note: Galton, Watson, and the Problem of Family Names

Waring's Theorem and Inclusion-Exclusion

Quick Check

Galton-Watson Branching Process

Compound Distribution

Definition:
Galton-Watson Branching Process

Theorem: PGF of the $n$ -th Generation