Ferkans — Interactive Telecom Tutor

A Transform Tailored to Counting

For random variables that take values in $\{0, 1, 2, \ldots\}$ — the number of arrivals in a time slot, the number of errors in a codeword, the population size in a branching process — there is a transform even more natural than the MGF. The probability generating function encodes the entire PMF as the coefficients of a power series, and its algebraic properties make it the ideal tool for compound sums and branching processes.

Definition:
Probability Generating Function (PGF)

Let $X$ be a random variable taking values in $\{0, 1, 2, \ldots\}$ with PMF $p_X[i] = \mathbb{P}(X = i)$ . The probability generating function of $X$ is

$G_X(s) = \sum_{i=0}^{\infty} p_X[i]\,s^i = \mathbb{E}[s^X], \qquad s \in \mathbb{C}.$

The series converges absolutely for $|s| \leq 1$ (since $\sum |p_X[i]|\,|s|^i \leq \sum p_X[i] = 1$ ).

The PGF connects to the other transforms: $G_X(e^t) = M_X(t)$ and $G_X(e^{ju}) = \phi_X(u)$ . Also, $G_X(0) = p_X[0]$ and $G_X(1) = 1$ .

Probability Generating Function (PGF)

For a nonnegative integer-valued RV $X$ : $G_X(s) = \mathbb{E}[s^X] = \sum_{i=0}^{\infty} p_X[i]\,s^i$ . The PMF is recovered via $p_X[i] = G_X^{(i)}(0)/i!$ .

Theorem: Moments and Factorial Moments from the PGF

Let $G_X(s)$ be the PGF of $X$ . Then:

$\mathbb{E}[X] = G_X'(1)$ .
The $k$ -th factorial moment is $\mathbb{E}[X(X-1)\cdots(X-k+1)] = G_X^{(k)}(1)$ .
$\text{Var}(X) = G_X''(1) + G_X'(1) - [G_X'(1)]^2$ .

Proof

Differentiate the power series

$G_X'(s) = \sum_{i=1}^{\infty} i\,p_X[i]\,s^{i-1}$ . Setting $s = 1$ : $G_X'(1) = \sum i\,p_X[i] = \mathbb{E}[X]$ .

Similarly, $G_X^{(k)}(s) = \sum_{i=k}^{\infty} i(i-1)\cdots(i-k+1)\,p_X[i]\,s^{i-k}$ , so $G_X^{(k)}(1) = \mathbb{E}[X(X-1)\cdots(X-k+1)]$ .

Variance formula

$\mathbb{E}[X^2] = \mathbb{E}[X(X-1)] + \mathbb{E}[X] = G_X''(1) + G_X'(1)$ .

$\text{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = G_X''(1) + G_X'(1) - [G_X'(1)]^2$ .

PGFs of Common Discrete Distributions

Distribution	$G_X(s)$	$\mathbb{E}[X]$	$\text{Var}(X)$
Constant $X = c$	$s^c$	$c$	$0$
$\text{Bernoulli}(p)$	$1-p+ps$	$p$	$p(1-p)$
$\text{Bin}(n,p)$	$(1-p+ps)^n$	$np$	$np(1-p)$
$\text{Geometric}(p)$	$\frac{ps}{1-s(1-p)}$	$1/p$	$(1-p)/p^2$
$\text{Poi}(\lambda)$	$e^{(s-1)\lambda}$	$\lambda$	$\lambda$

Example: Sum of Independent Poisson Random Variables

Let $X \sim \text{Poi}(\lambda)$ and $Y \sim \text{Poi}(\mu)$ be independent. Find the distribution of $Z = X + Y$ .

Solution

Multiply the PGFs

$G_Z(s) = G_X(s)\,G_Y(s) = e^{(s-1)\lambda}\,e^{(s-1)\mu} = e^{(s-1)(\lambda + \mu)}$ .

Identify by uniqueness

This is the PGF of $\text{Poi}(\lambda + \mu)$ . By the uniqueness theorem, $Z \sim \text{Poi}(\lambda + \mu)$ .

The sum of independent Poissons is Poisson with rate equal to the sum of the rates. This is the Poisson superposition property — when multiple independent Poisson streams merge, the combined stream is still Poisson.

Example: A Combinatorial Identity via PGF

Use probability generating functions to prove: $\sum_{i=0}^{n}\binom{n}{i}^2 = \binom{2n}{n}$ .

Solution

Set up the probabilistic argument

Let $X, Y \sim \text{Bin}(n, 1/2)$ independently. Then $Z = X + Y \sim \text{Bin}(2n, 1/2)$ .

Compare coefficients of $s^n$

$G_Z(s) = G_X(s)G_Y(s) = \left(\frac{1+s}{2}\right)^{2n}$ .

The coefficient of $s^n$ in $G_Z(s)$ is $\mathbb{P}(Z = n) = \binom{2n}{n}(1/2)^{2n}$ .

On the other hand, the coefficient of $s^n$ in $G_X(s)G_Y(s)$ is the convolution: $\sum_{i=0}^{n}\mathbb{P}(X=i)\mathbb{P}(Y=n-i) = \sum_{i=0}^{n}\binom{n}{i}(1/2)^n\binom{n}{n-i}(1/2)^n = (1/2)^{2n}\sum_{i=0}^{n}\binom{n}{i}^2$ .

Equating: $\sum_{i=0}^{n}\binom{n}{i}^2 = \binom{2n}{n}$ .

Quick Check

For a random variable $X$ with PGF $G_X(s)$ , what does $G_X(0)$ equal?

$\mathbb{P}(X = 0)$

$0$

$1$

$\mathbb{E}[X]$

Correction:

\mathbb{P}(X = 0)

$G_X(0) = \sum_{i=0}^{\infty} p_X[i]\cdot 0^i = p_X[0] = \mathbb{P}(X = 0)$ , since $0^0 = 1$ by convention and $0^i = 0$ for $i \geq 1$ .

The Probability Generating Function