Generating Function

A generating function is essentially a summary for a sequence of numbers. It's a formal power series where the coefficients encode a sequence of numbers, $a_{0}, a_{1}, a_{2}, \dots$ .
The ordinary generating function for a sequence ${a_{n}}_{n = 0}^{\infty}$ is the power series:

G (z) = \sum_{n = 0}^{\infty} a_{n} z^{n}

There is also a continuous analogue. If instead of a sequence one has a function $f (x)$ , the discrete sum can be replaced by an integral:

G (z) = \int_{0}^{\infty} f (x) z^{x} d x .

This plays the role of a continuous generating function, directly paralleling the discrete case.
When one reparametrizes with $z = e^{- s}$ , this construction becomes the Laplace transform:

G (e^{- s}) = \int_{0}^{\infty} f (x) e^{- s x} d x,

and related choices of weighting lead to other transforms such as the Mellin transform.

Application in probability theory

For a discrete random variable $X$ that takes non-negative integer values ${0, 1, 2, \dots}$ , we can define a Probability Generating Function (PGF). Here, the sequence of numbers is the probability mass function (PMF) of $X$ , where $p_{k} = P (X = k)$ .

The PGF of $X$ is defined as:

G_{X} (z) = E [z^{X}] = \sum_{k = 0}^{\infty} P (X = k) z^{k} = \sum_{k = 0}^{\infty} p_{k} z^{k}

Sum of independent random variables

This is where the magic happens. If you have two independent discrete random variables, $X$ and $Y$ , and you define a new variable $S = X + Y$ , the PGF of the sum $S$ is simply the product of the individual PGFs.

G_{S} (z) = G_{X + Y} (z) = G_{X} (z) \cdot G_{Y} (z)

This is incredibly useful because multiplying polynomials (or power series) is often much simpler than dealing with the distribution of the sum directly.

Relation to convolution

The process of finding the probability distribution of the sum of two independent random variables is equivalent to computing the convolution of their individual probability distributions.
Let $P (X = k) = p_{k}$ and $P (Y = k) = q_{k}$ . The PMF of the sum $S = X + Y$ is given by the discrete convolution of the sequences ${p_{k}}$ and ${q_{k}}$ :

P (S = n) = \sum_{k = 0}^{n} P (X = k) P (Y = n - k) = \sum_{k = 0}^{n} p_{k} q_{n - k}

This sum is precisely the coefficient of the $z^{n}$ term when you multiply the two power series $G_{X} (z)$ and $G_{Y} (z)$ together.
In short: multiplication of generating functions corresponds to the convolution of their coefficient sequences.