Composing probability generating functions

Question

How should one interpret the $n$-fold iteration (i.e. composition) $g(g( \cdots g(s))))$ of a probability generating function $g(s)$?

I'm looking at a proof that seems to suggest that if we have $m$ i.i.d. random variables $X_1, \ldots, X_m$ that are distributed like $G$, where $g(s)$ is the probability generating function of $G$, then the distribution $X_1 + \cdots + X_m$ has the generating function $g^m(s)$. I can't seem to prove it without trying to brute force the calculation for the composition and showing it is what we expect (is there a more elegant way to see this?) – why is this true?

Answer 1

The PGF of the sum of $X_1,\ldots,X_n$ independent but not necessarily identically distributed is given by $E[s^{\sum_{i=1}^n X_i}] = E[ s^{X_1} \ldots s^{X_n}] = E[s^{X_1}] \ldots E[s^{X_n}] = g_1(s) \ldots g_n(s)$ where $g_i$ is the PGF of $X_i$. If they are i.i.d. then you have $(g(s))^n$ as desired.

As for a case where you get a composition of PGF's, see Mark's link in the comments -- its a property of the structure of that problem.

Answer 2

Such a result occurs in discrete branching process. Here, the size of the n-th generation is defined by:$$X_{n}=\sum_{k=0}^{X_{n-1}}Y_{k},$$ where $Y_{k}$ is the offspring distribution of the k-th individual and all $Y_{k}$'s are iid random variables..

Under the assumptions of the discrete branching process, it can be shown that $$P\{X_{n}=k\mid X_{n-1}=j\}=P\{Y_1+Y_2+\cdots +Y_j\}$$ From which, we obtain $$P\{X_n=k\}=\sum_{j=0}^\infty P\{Y_1+Y_2+\cdots +Y_j\}\cdot P\{X_{n-1}=j\}$$ Let $\phi_n(s)$ denote the PGF of the size of the $n$-th generation, and $\phi(s)$ denotes the PGF of the of spring distribution, then by definition, $$\phi_n(s)=\sum_{k=0}^{X_{n-1}}P(X_n=k)s^k, |s|<1$$ can be shown to be $\phi_n(s)=\phi_{n-1}(\phi(s)).$

On iteration, it can be shown that $\phi_n(s) = \phi(\phi(\cdots\phi(s)\cdots))$, where $\phi(s)$ is the probability generating function of the offspring distribution.