0.1 Probability Generating Functions
The probability generating function of a random variable \(X\) is the power series representation of the mass function of the random variable. It is used when working with discrete non-negative integer valued random variables where it is well defined for at least \(|s|\leq 1\) (see below).
The probability generating function (PGF) of a non-negative, integer valued random variable \(X\) with mass function \(p_{X}(k)=\mathbb{P}(X=k)\) is defined as \[ G_{X}(s):=\mathbb{E}[s^X]=\sum_{k=0}^\infty s^kp_{X}(k). \]
The PGF is a power series with radius of convergence at least equal to 1 and so we can differentiate as many times as we wish by the interchange of summation and differentiation to obtain \[ G_{X}^{(n)}(s)=\sum_{k=n}^\infty k\cdot (k-1)\cdot \dots \cdot (k-n+1)s^{k-n}p_{X}(k)=\sum_{k=n}^\infty \frac{k!}{(k-n)!}s^{k-n}p_{X}(k). \] Rearranging we obtain the following result for returning the distribution function from the generator \[ p_{X}(n)=\frac{1}{n!}G_{X}^{(n)}(0). \] Generally, the PGF has 5 main uses:
- Computing mass functions of sums of independent non-negative integer-valued RVs;
- Computation of moments;
- Computation of limiting distributions using continuity theorems;
- Aiding in solving difference equations or recursions; and
- Aiding in solving linked systems of differential-difference equations.
For independent \(X\) and \(Y\) with PGFs \(G_{X}\) and \(G_{Y}\) respectively their sum has PGF \[ G_{X+Y}(s)=G_{X}(s)\cdot G_{Y}(s). \]
Proof: Firstly, we consider the discrete case. Since \(X\) and \(Y\) are independent we can write the PMF of \(X+Y\) as the convolution \(p_{X+Y}=p_{X}*p_{Y}\). From generating functions of convolutions the result follows.
In the continuous case, since \(X\) and \(Y\) are independent the PDF of \(Z=X+Y\) can be obtained by the convolutions of functions \[ f_{Z}(z)=f_{X}*f_{Y}(z)=\int _{\infty}^\infty f_{X}(x)f_{Y}(z-x) \, dx . \] The PGF is therefore \[ \begin{align} G_{Z}(s) & = \mathbb{E}s^Z \\ & = \int _{-\infty}^\infty s^Zf_{Z}(z) \, dz \\ & = \int _{-\infty}^\infty s^{X+Y}\int _{-\infty}^\infty f_{X}(x)f_{Y}(z-x) \, dx \, dz \\ & = \int _{-\infty}^\infty s^Xs^Y \, \int_{-\infty}^{\infty}f_{X}(x)f_{Y}(y) \, dx \, dy \\ & = \int _{-\infty}^\infty s^Yf_{Y}(y) \, dy \, \cdot \int _{-\infty}^\infty s^Xf_{X}(x) \, dx \\ & = G_{X}(s) \cdot G_{Y}(s). \end{align} \]
To recover the factorial moments from the generator we use the result \[ \mathbb{E}X=G_{X}'(1);\quad \mathbb{E}[X(X-1)\dots(X-k+1)]=G_{X}^{(k)}(1). \]
Let \(X\) be an integer-valued, non-negative random variable. The generating function \(G_{X}(s)\) is well-defined for \(s\leq 1\) or for a large interval around \(s=0\).
\begin{proof} Consider \(|s|\leq 1\). Then we have that \[\begin{aligned}|G_{X}(s)| & = \left|\sum_{{i=0}}^\infty s^ip_{X}(i)\right|\leq \sum_{i=0}^\infty |s|^ip_{X}(i)\stackrel{|s|\leq 1}\leq \sum_{i=0}^\infty p_{X}(i)=1.\end{aligned}\]\end{proof}
If \(\mathbb{P}(X\geq 2)\) then the PGF \(G_{X}(s)\) is convex on \(0\leq s\leq 1\).
\begin{proof} The second derivative of \(G_{X}(s)\) is given by \[
G_{X}^{(2)}=\sum_{i=1}^\infty i (i-1)p_{X}(i)s^{i-2}.
\] If \(p_{X}(i)>0\) for some \(i\geq 2\), then for all \(s\geq 0\), \(G_{X}^{(2)}(s)\geq 0\) hence \(G_{X}\) is convex.\end{proof}
Let \(X_{1}, \dots, X_{n}\) be independent with PGFs \(G_{1}, \dots, G_{n}\) respectively. The PGF of the sum \(S_{n}=\sum_{i=1}^nX_{i}\) is given by \[ G_{S_{n}}(s)=\prod_{i=1}^nG_{X_{i}}(s). \] Now let \(X_{1}, \dots, X_{n}\) be i.i.d. with PGF \(G_{X}\). Let \(N\geq 0\) be an independent integer-valued RV with PGF \(G_{N}\). The sum of random number \(N\) of terms has PGF \[ G_{S_{N}}(t)=G_{N}(G_{X}(t)). \]
\begin{proof} The proof of the first result follows from iteratively applying [[]]. For the second result, by conditioning on \(N\) and applying the [[tower-property|tower property]] we obtain \[
\begin{align}
G_{S_{N}}(t) & = \mathbb{E}(t^{S_{N}}) \\
& = \mathbb{E}[\mathbb{E}[t^{S_{N}}|N]] \tag{Tower property}\\
& = \sum_{n=0}^\infty \mathbb{P}(N=n)\mathbb{E}[t^{S_{n}}|N=n] \\
& = \sum_{n=0}^\infty \mathbb{E}[t^{S_{n}}]p_{N}(n) \tag{independence of $N$ and $S_{n}$} \\
& = \sum_{n=0}^\infty G_{S_{n}}(t)p_{N}(n) \\
& = \sum_{n=0}^\infty(G_{X}(t))^np_{N}(n) \\
& = G_{N}(G_{X}(t)),
\end{align}
\] where the last line holds from the first result. \end{proof}
Let \(X_{1}, \dots, X_{n}\) be i.i.d. with PGF \(G_{X}\) and mean \(\mathbb{E}X\). Let \(N\geq 0\) be an integer-valued RV which is independent of all \(X_i\) with PGF \(G_{N}\) and mean \(\mathbb{E}N\). The expectation of the sum \(S_{N}=\sum_{i=1}^NX_{i}\) is given by \[ \mathbb{E}S_{N}=\mathbb{E}N \cdot \mathbb{E}X. \]
\begin{proof} By recovering the factorial moments of the PGF we see that we need to take the derivative at \(s=1\) of the PGF of \(S_{N}\), remembering that \(G_{X}(1)=1\), \(EX=G_{X}^{(1)}\) and \(\mathbb{E}N=G_{N}^{(1)}(1)\). We have that \[
\begin{align}
\mathbb{E}S_{N} & = G_{S_{N}}^{(1)}(1) \\
& = (G_{N}(G_{X}(t)))^{(1)}|_{t=1} \\
& = G_{N}^{(1)}(G_{X}(t)) \cdot G_{X}^{(1)}(t)|_{t=1} \\
& = G_{N}^{(1)}(1) \cdot G_{X}^{(1)}(1) \\
& = \mathbb{E}N \cdot \mathbb{E}X.
\end{align}
\]