Why PGFs Simplify Sums
Adding independent counts often produces a distribution that is easier to calculate than it first appears. A direct approach lists all combinations of component values that could give the desired total. A probability generating function (PGF) packages those probabilities as coefficients of a power series. For independent counts, multiplying the PGFs automatically combines all the ways their values can add to a given total.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). A random variable \(X\) is nonnegative integer-valued if it takes values in \(\{0,1,2,\ldots\}\) with probability one. Write \(p_k=\mathbb{P}(X=k)\). Its PGF is the function \(G_X\) defined by \(G_X(s)=\mathbb{E}[s^X]\) for \(0\le s\le1\), where \(0^0\) is defined to be \(1\). In particular, \(G_X(0)=\mathbb{P}(X=0)\), and \(G_X(1)=1\). Expanding the expectation by the possible values of \(X\) gives \(G_X(s)=\sum_{k=0}^{\infty}p_ks^k\).
The second formula is the convolution rule: it adds the probabilities of every combination of component counts that has the specified total. It also tells us precisely how to recover the sum distribution from the PGF product: the probability at \(k\) is the coefficient of \(s^k\).
Proof. Fix \(s\in[0,1]\). Since \(X_1,\ldots,X_n\) are nonnegative integer-valued, partitioning the sample space according to their values gives $$ G_{S_n}(s)=\sum_{k_1,\ldots,k_n\ge0}s^{k_1+\cdots+k_n}\mathbb{P}(X_1=k_1,\ldots,X_n=k_n). $$ Mutual independence means that the joint probability in each term is \(\prod_{r=1}^n\mathbb{P}(X_r=k_r)\). Also, \(s^{k_1+\cdots+k_n}=\prod_{r=1}^n s^{k_r}\). Thus the summand factors into \(\prod_{r=1}^n\big(s^{k_r}\mathbb{P}(X_r=k_r)\big)\). All terms are nonnegative, so the multiple sum can be rearranged and factored as the product of the \(n\) sums: $$ G_{S_n}(s)=\prod_{r=1}^{n}\left(\sum_{k_r=0}^{\infty}s^{k_r}\mathbb{P}(X_r=k_r)\right)=\prod_{r=1}^{n}G_{X_r}(s). $$ This reasoning includes \(s=0\), with the stated convention for \(0^0\), and \(s=1\), when each series sums to one. For the probability formula, the event \(S_n=k\) is the disjoint union of the events \(\{X_1=k_1,\ldots,X_n=k_n\}\) over nonnegative integer tuples with \(k_1+\cdots+k_n=k\). There are finitely many such tuples, since each \(k_r\) must be at most \(k\). Add their probabilities and use independence on each event to obtain the stated sum. \(\square\)
For \(n=1\), the identities reduce to \(G_{X_1}=G_{X_1}\) and \(\mathbb{P}(X_1=k)=\mathbb{P}(X_1=k)\). If one also defines an empty sum as zero, its PGF is \(1\), the empty product. The theorem requires mutual independence; it is not enough that the variables have PGFs or that their marginal distributions are known.
Using the Product to Find a Distribution
For finite-support variables, each PGF is a polynomial, and multiplying polynomials gives the sum distribution directly. For variables with infinitely many possible values, the PGF may be an infinite series, but the coefficient at any fixed \(k\) still receives contributions from only finitely many nonnegative integer tuples. The examples below illustrate both settings.
Worked Example: Two Independent Poisson Counts
Let \(X\) and \(Y\) be independent Poisson variables with respective parameters \(2\) and \(3\). Find the distribution of \(S=X+Y\).
For a Poisson variable with parameter \(\lambda>0\), its mass at \(r\ge0\) is \(e^{-\lambda}\lambda^r/r!\). Summing these masses against \(s^r\) gives $$ G(s)=\sum_{r=0}^{\infty}e^{-\lambda}\frac{\lambda^r}{r!}s^r =e^{-\lambda}\sum_{r=0}^{\infty}\frac{(\lambda s)^r}{r!} =e^{\lambda(s-1)}. $$ Thus \(G_X(s)=e^{2(s-1)}\) and \(G_Y(s)=e^{3(s-1)}\). Independence and the theorem give $$ 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. $$ Therefore, for every \(k\ge0\), \(\mathbb{P}(S=k)=e^{-5}5^k/k!\).
Check by convolution. For a fixed \(k\), the convolution formula gives $$ \begin{aligned} \mathbb{P}(S=k) &=\sum_{r=0}^{k}e^{-2}\frac{2^r}{r!}\,e^{-3}\frac{3^{k-r}}{(k-r)!}\\ &=\frac{e^{-5}}{k!}\sum_{r=0}^{k}\binom{k}{r}2^r3^{k-r} =\frac{e^{-5}}{k!}(2+3)^k =e^{-5}\frac{5^k}{k!}. \end{aligned} $$ This agrees with the PGF coefficient. The probabilities sum to \(e^{-5}\sum_{k\ge0}5^k/k!=e^{-5}e^5=1\), so the formula gives a probability distribution.
Worked Example: Two Bernoulli Counts with Different Success Probabilities
Let \(X\) and \(Y\) be independent, with \(\mathbb{P}(X=1)=\tfrac13\), \(\mathbb{P}(X=0)=\tfrac23\), \(\mathbb{P}(Y=1)=\tfrac12\), and \(\mathbb{P}(Y=0)=\tfrac12\). Find the distribution of \(S=X+Y\).
The PGFs are \(G_X(s)=\tfrac23+\tfrac13s\) and \(G_Y(s)=\tfrac12+\tfrac12s\). Their product is $$ G_S(s)=\left(\tfrac23+\tfrac13s\right)\left(\tfrac12+\tfrac12s\right) =\tfrac13+\tfrac12s+\tfrac16s^2. $$ The coefficients give \(\mathbb{P}(S=0)=\tfrac13\), \(\mathbb{P}(S=1)=\tfrac12\), and \(\mathbb{P}(S=2)=\tfrac16\). All other values have probability zero.
Check by listing the possible pairs. The total is zero only for \((X,Y)=(0,0)\), which has probability \(\tfrac23\cdot\tfrac12=\tfrac13\). The total is one for \((1,0)\) or \((0,1)\), whose probabilities are \(\tfrac13\cdot\tfrac12=\tfrac16\) and \(\tfrac23\cdot\tfrac12=\tfrac13\); their sum is \(\tfrac12\). The total is two only for \((1,1)\), of probability \(\tfrac13\cdot\tfrac12=\tfrac16\). Finally, the probabilities sum to \(\tfrac13+\tfrac12+\tfrac16=1\), as required.
Worked Example: A Sum with Two Different Supports
Let \(X\) and \(Y\) be independent. Suppose \(X\) is \(0\) or \(2\), each with probability \(\tfrac12\), while \(Y\) is \(0\) with probability \(\tfrac13\) and \(1\) with probability \(\tfrac23\). Find the distribution of \(S=X+Y\).
The PGFs are \(G_X(s)=\tfrac12+\tfrac12s^2\) and \(G_Y(s)=\tfrac13+\tfrac23s\). Therefore, $$ G_S(s)=\left(\tfrac12+\tfrac12s^2\right)\left(\tfrac13+\tfrac23s\right) =\tfrac16+\tfrac13s+\tfrac16s^2+\tfrac13s^3. $$ Hence \(\mathbb{P}(S=0)=\tfrac16\), \(\mathbb{P}(S=1)=\tfrac13\), \(\mathbb{P}(S=2)=\tfrac16\), and \(\mathbb{P}(S=3)=\tfrac13\).
Check by the four possible component pairs. The pairs \((0,0),(0,1),(2,0),(2,1)\) give totals \(0,1,2,3\), respectively. Their probabilities, using independence, are \(\tfrac12\cdot\tfrac13=\tfrac16\), \(\tfrac12\cdot\tfrac23=\tfrac13\), \(\tfrac12\cdot\tfrac13=\tfrac16\), and \(\tfrac12\cdot\tfrac23=\tfrac13\). These match the polynomial coefficients and sum to \(\tfrac16+\tfrac13+\tfrac16+\tfrac13=1\).
What the Product Rule Does—and Does Not—Say
The product rule is useful because it replaces a potentially long enumeration of outcomes with algebra. If the component PGFs are known, one can multiply them and read the coefficients. For an \(n\)-variable sum, it is often practical to multiply one PGF at a time; the theorem applies to the whole mutually independent collection, and ordinary polynomial multiplication performs the same successive convolutions.
A PGF records probabilities, not just a convenient symbolic expression. For a finite polynomial, its coefficient at \(s^k\) is directly the probability of the value \(k\). For an infinite PGF, the theorem and the convolution formula identify the coefficient at every fixed \(k\). The PGF identity alone does not make dependent variables independent, nor does it justify multiplying marginal PGFs when dependence is present.
Common mistake: multiplying marginal PGFs without independence. Let \(X=Y\), where \(X\) is Bernoulli with success probability \(\tfrac12\). Then each marginal PGF is \(\tfrac12+\tfrac12s\). Multiplying the marginal PGFs incorrectly would give $$ \left(\tfrac12+\tfrac12s\right)^2 =\tfrac14+\tfrac12s+\tfrac14s^2, $$ which predicts a positive probability \(\tfrac12\) that \(X+Y=1\). But \(X=Y\), so the sum is \(0\) when \(X=0\) and \(2\) when \(X=1\); it can never equal \(1\). The correct PGF is \(\mathbb{E}[s^{X+Y}]=\tfrac12+\tfrac12s^2\). The error is precisely the unjustified factorization: knowing the two marginal distributions does not give the joint probabilities needed for the sum when the variables are dependent.
In calculations, check both the assumptions and the resulting coefficients. Verify mutual independence before using the product identity, ensure the coefficient list covers all possible totals, and check that the probabilities are nonnegative and sum to one. In a finite example, direct enumeration is a useful independent check of the polynomial multiplication.
Check Your Understanding
Use the product identity and, where appropriate, verify your coefficients by the convolution formula.
- Suppose \(X\) and \(Y\) are independent Bernoulli variables with success probabilities \(\tfrac14\) and \(\tfrac34\). Find the PGF and the probabilities of \(X+Y=0,1,2\).
- Two independent Poisson variables have parameters \(1\) and \(4\). Use their PGFs to identify the distribution of their sum.
- For independent nonnegative integer-valued \(X_1,X_2,X_3\), write the convolution formula for \(\mathbb{P}(X_1+X_2+X_3=2)\), listing every nonnegative integer triple that contributes.
- In the dependent example \(X=Y\) with \(X\) Bernoulli of parameter \(\tfrac12\), compute the probabilities that the sum is \(0,1,2\), and explain why the product of marginal PGFs gives a different answer.
- Why does the coefficient formula for a fixed total \(k\) involve only finitely many tuples, even when the component variables have infinite support?