What Is the PGF of a Sum?

Suppose $X$ and $Y$ are independent, non-negative integer-valued random variables.

Write their probability sequences as

$$p_n=\mathbb{P}(X=n)$$

and

$$q_n=\mathbb{P}(Y=n).$$

Their probability generating functions are

$$P_X(z)=\sum_{n=0}^{\infty}p_nz^n$$

and

$$P_Y(z)=\sum_{n=0}^{\infty}q_nz^n.$$

We are interested in the distribution of the sum

$$X+Y.$$

The key result is

$$P_{X+Y}(z)=P_X(z)P_Y(z).$$

So, when we add independent random variables, we multiply their PGFs.

We will see why this works below.

Example: Finding $\mathbb{P}(X+Y=3)$

Let’s suppose we want to find

$$\mathbb{P}(X+Y=3).$$

There are four ways this can happen:

$$X=0,\qquad Y=3,$$

$$X=1,\qquad Y=2,$$

$$X=2,\qquad Y=1,$$

or

$$X=3,\qquad Y=0.$$

Since $X$ and $Y$ are independent, we can multiply the probabilities within each pair.

This gives

$$\mathbb{P}(X+Y=3)=p_0q_3+p_1q_2+p_2q_1+p_3q_0.$$

We simply sum over all combinations of values that add up to $3$.

The Convolution Formula

The same idea works for any value $n$.

If $X=k$, then we need $Y=n-k$ for the sum to equal $n$ overall.

We consider every possible value we could assign to $X$:

$$k=0,1,\dots,n.$$

This gives

$$\mathbb{P}(X+Y=n)=\sum_{k=0}^{n}p_kq_{n-k}.$$

This calculation combines all pairs of probabilities whose corresponding values add up to the total we want. As $n$ varies, the resulting sequence

$$c_n = \sum_{k=0}^{n}p_kq_{n-k}$$

is called the convolution of the two original sequences.

Why Does Multiplying the PGFs Work?

Now consider the product

$$P_X(z)P_Y(z).$$

Writing out the two power series,

$$P_X(z)P_Y(z)=(p_0+p_1z+p_2z^2+\dots)(q_0+q_1z+q_2z^2+\dots).$$

Multiplying them gives

$$P_X(z)P_Y(z)=p_0q_0+(p_0q_1+p_1q_0)z+(p_0q_2+p_1q_1+p_2q_0)z^2+\dots$$

Look at the coefficients.

The coefficient of $z^0$ is

$$p_0q_0=\mathbb{P}(X+Y=0).$$

The coefficient of $z^1$ is

$$p_0q_1+p_1q_0=\mathbb{P}(X+Y=1).$$

The coefficient of $z^2$ is

$$p_0q_2+p_1q_1+p_2q_0=\mathbb{P}(X+Y=2).$$

The coefficient of $z^3$ is

$$p_0q_3+p_1q_2+p_2q_1+p_3q_0=\mathbb{P}(X+Y=3).$$

In general, the coefficient of $z^n$ is

$$\sum_{k=0}^{n}p_kq_{n-k}=\mathbb{P}(X+Y=n).$$

These are exactly the coefficients required for the PGF of $X+Y$.

Hence

$$P_{X+Y}(z)=P_X(z)P_Y(z).$$

This is the useful connection: multiplying the two PGFs automatically carries out the convolution of the two probability sequences.

If the two original PGFs are still given as power series, this is useful because multiplying out power series feels familiar and is less confusing than computing a convolution directly.

However, if we actually have closed-form expressions for the power series, multiplying them together is trivial!

Sums of IID Random Variables

An especially common situation in statistics is that we have $n$ random variables

$$X_1,X_2,\dots,X_n,$$

all independent and with the same distribution (IID).

If these $X_i$ are non-negative and integer-valued, they all have the same PGF, say $P_X(z)$.

Applying the previous result repeatedly gives

$$P_{X_1+\dots+X_n}(z)=\left(P_X(z)\right)^n.$$

So, instead of taking convolutions again and again, we can simply raise one PGF to the $n$th power.

Sums like this appear constantly in probability and statistics.

For example, sample averages are built from them:

$$\bar{X}=\frac{X_1+\dots+X_n}{n}.$$

Understanding sums of IID random variables is one of the main reasons generating functions are useful.

Background:

• Summing Two Random Variables: Convolutions

• Probability Generating Functions