Generating functions

Write a die as a polynomial, one power of $z$ per face. Watch the polynomial multiply by itself: its numbers become the chances of two dice.

A die as a polynomial

On the page Sums of random variables, the chances of a two-dice total came from sliding one die’s chances along the other’s: a convolution. That works, but it is slow to do by hand, and slower for three dice. Here is a trick that does it by ordinary multiplication.

Write the chances of a die as the numbers in front of the powers of a letter $z$, one power per face:

The letter $z$ is only a place-holder: the power says which face, and the number in front says its chance. Now multiply $G(z)$ by itself. A term $\tfrac16z^a$ from the first copy times a term $\tfrac16z^b$ from the second gives $\tfrac1{36}z^{a+b}$: the powers add, as the faces do. So the number in front of $z^7$ in $G(z)^2$ collects every pair of faces that adds up to 7. There are six of them, so it is $\tfrac6{36}$, the chance of a total of 7.

Multiplying the polynomials did the convolution for me. That is the picture at the top of the page.

The generating function

For any random variable $X$ that takes whole-number values $k=0,1,2,\dots$, the generating function is

The second form says the same thing: it is the mean of $z^X$. A coin that lands heads ($X=1$) with chance $p$ has $G_X(z)=(1-p)+pz$. Putting $z=1$ adds up all the chances, so $G_X(1)=1$ for every $X$.

The product rule. If $X$ and $Y$ are independent, then

The third step uses independence: the mean of a product of independent variables is the product of their means. So adding independent variables multiplies their generating functions. For $n$ coin flips, the number of heads has $G(z)=(1-p+pz)^n$, the generating function of $\mathrm{Bin}(n,p)$.

A common slip is to add the generating functions instead. Adding them does not describe a sum of variables at all.

Moments from derivatives

The generating function also holds the mean and variance. Differentiate:

Differentiate again and put $z=1$: $G_X''(1)=\sum_k k(k-1)\,p_X(k)=\mathbb{E}\{X(X-1)\}$. Since $\mathrm{Var}\{X\}=\mathbb{E}\{X^2\}-\mathbb{E}\{X\}^2$ and $\mathbb{E}\{X^2\}=\mathbb{E}\{X(X-1)\}+\mathbb{E}\{X\}$,

For one die, $G'(1)=\tfrac16(1+2+3+4+5+6)=\tfrac{21}6=3.5$ and $G''(1)=\tfrac16(0+2+6+12+20+30)=\tfrac{70}6=11.67$. So the variance is $11.67+3.5-12.25=2.917$, which is $\tfrac{35}{12}$, the die’s variance.

For $n$ dice, $G(z)^n$ gives mean $3.5n$ and variance $\tfrac{35}{12}n$, as the readouts show when you drag the number of dice after the clip. With three dice, the mean is 10.5 and the variance is 8.75.

Two relatives

The same idea works with other functions in place of $z^X$.

The moment generating function is $M_X(t)=\mathbb{E}\{e^{tX}\}$. It is the generating function with $z=e^t$, and it works for variables that are not whole numbers. Its derivative at $t=0$ is the mean.

The characteristic function is $\chi_X(\Omega)=\mathbb{E}\{e^{j\Omega X}\}$, where $j$ is the square root of $-1$, as in the signal processing pages. It always exists, even when $M_X$ does not, and it is the tool behind the usual proof of The central limit theorem. The product rule holds for both: adding independent variables multiplies their functions.

Worked example

1. One die. $G'(1)=3.5$, $G''(1)=70/6=11.67$, variance $11.67+3.5-12.25=2.917$.
2. Two dice. The number in front of $z^7$ in $G(z)^2$ is $\tfrac6{36}$; in front of $z^{12}$ it is $\tfrac1{36}$.
3. Three dice. The chances of 10 and of 11 are both $\tfrac{27}{216}=0.125$. The mean is 10.5 and the variance 8.75.
4. A coin. $G(z)=1-p+pz$, so $G'(1)=p$, the mean.
5. Binomial. $n$ flips: $G(z)=(1-p+pz)^n$.
6. Always. $G_X(1)=1$.

Where you’ll meet this

Generating functions turn counting problems into algebra: how many ways a total can be made from coins or dice, for example. They give the chance that a family name dies out, where each person has a random number of children and the generating function of the whole tree is built by substituting one generating function into another. And they give exact distributions of sums where simulation gives only estimates.

Reference card