PGFs of Independent Integer-Valued Sums

Why PGFs Simplify Sums

When independent counts are added, finding the distribution directly can require many cases. A probability-generating function packages all the probabilities into one power series. Independence turns the PGF of a sum into a product, and multiplying series performs exactly the convolution needed to obtain the probabilities of that sum.

The product rule is useful both for exact distributions and for moments. It can show, for example, that a sum of independent Poisson variables is Poisson, or that the sum of independent geometric counts has a simple coefficient formula. The key is to keep track of what the coefficients mean.

Definition: If \(X\) is a nonnegative integer-valued random variable, its probability-generating function (PGF) is

G_X(s)=E[s^X]=\sum_{k=0}^{\infty}P(X=k)s^k,\qquad 0\leq s\leq 1.

The same power series converges for \(|s|<1\). Its coefficient of \(s^k\) is the probability \(P(X=k)\); we write this coefficient as \([s^k]G_X(s)\).

For independent random variables \(X_1,\ldots,X_n\), each taking values in the nonnegative integers, let \(S=X_1+\cdots+X_n\). The fundamental rule is as follows.

Theorem: If \(X_1,\ldots,X_n\) are independent nonnegative integer-valued random variables, then for \(0\leq s\leq 1\),

G_S(s)=\prod_{i=1}^{n}G_{X_i}(s).

Consequently, for each nonnegative integer \(k\),

P(S=k)=[s^k]\prod_{i=1}^{n}G_{X_i}(s) =\sum_{\substack{k_1+\cdots+k_n=k\\ k_i\geq 0}} \prod_{i=1}^{n}P(X_i=k_i).

Why Independence Gives a Product

For a fixed total \(k\), the possible ways for the summands to add to \(k\) are the tuples \((k_1,\ldots,k_n)\) of nonnegative integers with \(k_1+\cdots+k_n=k\). These are finitely many tuples. Independence makes the probability of each tuple a product of individual probabilities.

Write the event for the sum.
The event \(S=k\) is the disjoint union of the events \(X_1=k_1,\ldots,X_n=k_n\) over all tuples whose entries sum to \(k\).

Apply independence.
For each tuple, \(P(X_1=k_1,\ldots,X_n=k_n)=\prod_{i=1}^nP(X_i=k_i)\).

Read the coefficient.
In the product of the PGF power series, a term of degree \(k\) is formed by choosing terms whose degrees add to \(k\). The coefficient is the same sum of products.

Here is the argument in full. Since the events specifying the individual values are disjoint and \(S\) is integer-valued,

P(S=k)= \sum_{\substack{k_1+\cdots+k_n=k\\ k_i\geq 0}} P(X_1=k_1,\ldots,X_n=k_n) = \sum_{\substack{k_1+\cdots+k_n=k\\ k_i\geq 0}} \prod_{i=1}^nP(X_i=k_i).

On the other hand, multiplying the series for the individual PGFs shows that the coefficient of \(s^k\) in \(\prod_iG_{X_i}(s)\) is precisely that last sum. Thus the coefficient formula holds. Summing the probabilities with weights \(s^k\), or equivalently multiplying the nonnegative power series, gives \(G_S(s)=\prod_iG_{X_i}(s)\). The power series converge absolutely for \(|s|<1\), and at \(s=1\) both sides equal 1. This proves the PGF identity and the distribution formula. \(\square\)

This coefficient calculation is the discrete convolution rule: to obtain total \(k\), sum over every way to divide \(k\) among the summands. The PGF product records all such calculations at once. For two variables, the formula reduces to \(P(X_1+X_2=k)=\sum_{j=0}^kP(X_1=j)P(X_2=k-j)\).

Worked Distributions from PGF Products

Worked Example: Two Independent Bernoulli Counts

Let \(X\sim\operatorname{Bernoulli}(0.3)\) and \(Y\sim\operatorname{Bernoulli}(0.4)\), independently. Find the distribution of \(S=X+Y\).

The PGFs are \(G_X(s)=0.7+0.3s\) and \(G_Y(s)=0.6+0.4s\). Therefore

$$ G_S(s)=(0.7+0.3s)(0.6+0.4s) =0.42+0.46s+0.12s^2. $$

Reading off the coefficients gives \(P(S=0)=0.42\), \(P(S=1)=0.46\), and \(P(S=2)=0.12\). These probabilities sum to \(0.42+0.46+0.12=1\). As a direct check, \(S=1\) occurs when exactly one of \(X,Y\) equals 1: \(0.3(0.6)+0.7(0.4)=0.18+0.28=0.46\).

Worked Example: A Sum of Independent Poisson Counts

Let \(X\sim\operatorname{Poisson}(2)\) and \(Y\sim\operatorname{Poisson}(3)\), independently. Find the distribution of \(S=X+Y\).

For a Poisson variable with parameter \(\lambda\), its PGF is \(G(s)=e^{\lambda(s-1)}\), as follows by summing its probability series:

G_X(s)=\sum_{k=0}^{\infty}e^{-2}\frac{2^k}{k!}s^k =e^{-2}e^{2s}=e^{2(s-1)}.

Similarly, \(G_Y(s)=e^{3(s-1)}\). Independence gives

G_S(s)=e^{2(s-1)}e^{3(s-1)} =e^{5(s-1)} =e^{-5}\sum_{k=0}^{\infty}\frac{5^k}{k!}s^k.

Thus \(P(S=k)=e^{-5}5^k/k!\) for every \(k\geq0\), which is the \(\operatorname{Poisson}(5)\) distribution. The coefficients sum to \(e^{-5}e^5=1\), as required.

Worked Example: Adding Two Geometric Counts

Let \(X\) and \(Y\) be independent with \(P(X=k)=P(Y=k)=2^{-(k+1)}\) for \(k=0,1,\ldots\). Find the probability that \(S=X+Y\) equals \(k\).

For either variable, summing a geometric series gives

G_X(s)=G_Y(s)=\sum_{j=0}^{\infty}\frac{1}{2^{j+1}}s^j =\frac{1/2}{1-s/2},\qquad |s|<2.

The product is

G_S(s)=\frac{1}{4}\left(1-\frac{s}{2}\right)^{-2} =\frac{1}{4}\sum_{k=0}^{\infty}(k+1)\left(\frac{s}{2}\right)^k.

The last equality follows by differentiating the geometric series \((1-u)^{-1}=\sum_{j=0}^{\infty}u^j\) for \(|u|<1\), which gives \((1-u)^{-2}=\sum_{k=0}^{\infty}(k+1)u^k\). Substituting \(u=s/2\), the coefficient is

P(S=k)=\frac{k+1}{2^{k+2}},\qquad k=0,1,\ldots.

The formula gives \(P(S=0)=1/4\) and \(P(S=1)=1/4\). Its probabilities sum to 1, since \(\frac14\sum_{k=0}^{\infty}(k+1)/2^k=\frac14(1-1/2)^{-2}=1\).

Moments from the Product

PGF derivatives at 1 encode factorial moments: when the relevant moments are finite, \(G_X'(1)=E[X]\) and \(G_X''(1)=E[X(X-1)]\). For these identities at the boundary, derivatives can be understood as limits from below; termwise differentiation for \(s<1\), followed by monotone convergence as \(s\) increases to 1, justifies the formulas.

Theorem: If \(X_1,\ldots,X_n\) are independent nonnegative integer-valued random variables with finite second moments, then

E[S]=\sum_{i=1}^nE[X_i], \qquad \operatorname{Var}(S)=\sum_{i=1}^n\operatorname{Var}(X_i).

To derive these identities from the PGF product, write \(\mu_i=E[X_i]\) and \(\nu_i=E[X_i(X_i-1)]\). Differentiate the finite product for \(s<1\) and take the limits at 1. Since each \(G_{X_i}(1)=1\), the first derivative yields

G_S'(1)=\sum_{i=1}^nG_{X_i}'(1)=\sum_{i=1}^n\mu_i.

The second derivative has one term for each second derivative of a factor and two terms for each pair of distinct factors. Consequently,

G_S''(1)=\sum_{i=1}^n\nu_i+ 2\sum_{1\leq i<j\leq n}\mu_i\mu_j.

Since \(E[S^2]=G_S''(1)+G_S'(1)\), subtracting \(E[S]^2=(\sum_i\mu_i)^2\) gives

\begin{aligned} \operatorname{Var}(S) &=\sum_{i=1}^n(\nu_i+\mu_i-\mu_i^2)\\ &=\sum_{i=1}^n\left(E[X_i(X_i-1)]+E[X_i]-(E[X_i])^2\right)\\ &=\sum_{i=1}^n\left(E[X_i^2]-(E[X_i])^2\right) =\sum_{i=1}^n\operatorname{Var}(X_i). \end{aligned}

Here \(X_i(X_i-1)+X_i=X_i^2\). The finite-second-moment assumption ensures that these derivatives at 1 and the variance expressions are finite. This completes the derivation. \(\square\)

Worked Example: Checking Moments for the Geometric Sum

For the geometric variables in the preceding example, \(G_S(s)=\frac14(1-s/2)^{-2}\). Differentiating gives

G_S'(s)=\frac14(1-s/2)^{-3}, \qquad G_S''(s)=\frac38(1-s/2)^{-4}.

At \(s=1\), these are \(G_S'(1)=2\) and \(G_S''(1)=6\). Therefore \(E[S]=2\) and \(E[S^2]=G_S''(1)+G_S'(1)=8\), so \(\operatorname{Var}(S)=8-2^2=4\). This also agrees with adding the component moments: each variable has mean 1 and variance 2, giving mean 2 and variance 4 for the sum.

Common Mistake: Multiplying Without Independence

The PGF product rule requires independence. For a concrete failure, let \(X\) be Bernoulli with success probability \(1/2\), and set \(Y=X\). Each marginal PGF is \((1+s)/2\), but \(X\) and \(Y\) are dependent. Their sum is \(2X\), so its PGF is \((1+s^2)/2\), not the product of the marginal PGFs:

G_{X+Y}(s)=\frac{1+s^2}{2} \ne \left(\frac{1+s}{2}\right)^2.

The incorrect reasoning is to multiply the marginal PGFs merely because both variables have PGFs. The correction is to verify independence before factoring the joint probabilities. When independence does hold, multiplying PGFs is a compact way to carry out the full convolution; coefficient extraction then gives the exact distribution.

Key takeaway: For a finite independent sum of nonnegative integer-valued variables, multiply the individual PGFs and extract the coefficient of \(s^k\) to obtain \(P(S=k)\). When second moments are finite, differentiating the product also gives the sum’s mean and variance.

Check Your Understanding

Use PGF multiplication and coefficient extraction to answer these questions.

Two independent Bernoulli variables have success probabilities \(0.2\) and \(0.5\). What is the coefficient of \(s\) in the PGF of their sum, and what event does it represent?
Why does the coefficient of \(s^k\) in a product of two PGFs involve a sum over \(j=0,\ldots,k\)?
Two independent Poisson variables have parameters 1 and 4. What PGF does their sum have?
In the geometric-sum example, calculate \(P(S=2)\) from the coefficient formula.
Give an example showing why the product rule cannot be applied to dependent variables just from knowing their marginal PGFs.