PGFs for Identifying Integer-Valued Sums

Why Generate a Function for an Integer-Valued Sum?

When two independent variables take values in the nonnegative integers, the probability that their sum equals $k$ is a convolution: contributions come from every pair of values adding to $k$. A probability-generating function (PGF) packages all those probabilities as coefficients of one power series. Independence then turns the convolution into multiplication, and coefficient extraction recovers the probabilities of the sum.

The function is useful not because it removes the need to check a distribution, but because it makes the calculation systematic. Its coefficients must be probabilities, and its nonzero coefficients must agree with the possible values of the sum. Those support checks can expose a mistaken identification even when a proposed formula looks familiar.

Definition and Coefficient Notation

Definition: If $X$ is a random variable taking values in $\{0,1,2,\ldots\}$, its probability-generating function is $$ G_X(s)=E[s^X]=\sum_{j=0}^{\infty}P(X=j)s^j,\qquad |s|\leq 1. $$ The convention $s^0=1$, including at $s=0$, makes $G_X(0)=P(X=0)$. For a power series $H(s)$, $[s^k]H(s)$ denotes the coefficient of $s^k$ in its expansion about zero.

The series defining $G_X$ converges absolutely for $|s|\leq 1$, since $$ \sum_{j=0}^{\infty}P(X=j)|s|^j\leq \sum_{j=0}^{\infty}P(X=j)=1. $$ In particular, $G_X(1)=1$. For $|s|<1$, it is a power series and hence is analytic there. Most importantly, its coefficient at degree $j$ is exactly $P(X=j)$.

A PGF is therefore more than a convenient expression: it determines the distribution. If two PGFs agree throughout $|s|<1$, their power-series coefficients agree, so the corresponding random variables have the same probabilities at every nonnegative integer.

Independent Sums: Product and Coefficient Rules

Theorem: Let $X$ and $Y$ be independent random variables taking values in $\{0,1,2,\ldots\}$. Then $X+Y$ is also nonnegative integer-valued, and $$ G_{X+Y}(s)=G_X(s)G_Y(s),\qquad |s|\leq 1. $$ Consequently, for every $k\geq 0$, $$ P(X+Y=k)=[s^k]\{G_X(s)G_Y(s)\} =\sum_{j=0}^{k}P(X=j)P(Y=k-j). $$

Proof. For $|s|\leq 1$, $s^{X+Y}=s^Xs^Y$, with the usual interpretation at $s=0$. Independence gives $$ E[s^{X+Y}]=E[s^Xs^Y]=E[s^X]E[s^Y]. $$ The expectations exist because $|s^X|\leq 1$ and $|s^Y|\leq 1$. This proves the product identity. To obtain the coefficient formula, multiply the two power series. The coefficient of $s^k$ is the sum of all products whose degrees add to $k$: $$ [s^k]\left(\sum_{j=0}^{\infty}P(X=j)s^j \sum_{\ell=0}^{\infty}P(Y=\ell)s^\ell\right) =\sum_{j=0}^{k}P(X=j)P(Y=k-j). $$ Only finitely many terms contribute to this coefficient, so no infinite rearrangement is needed. Since $X+Y$ is nonnegative integer-valued, this coefficient is its probability at $k$. $\square$

For more than two independent variables, the same argument can be applied repeatedly: the PGF of the sum is the product of the individual PGFs. The coefficient at $k$ is the sum over all nonnegative integer tuples whose entries add to $k$, with each term the product of the corresponding probabilities.

Worked Example: Extracting a Finite-Support Sum

Let $X$ have probabilities $P(X=0)=1/2$, $P(X=1)=1/3$, and $P(X=2)=1/6$. Independently, let $Y$ have $P(Y=0)=3/4$ and $P(Y=2)=1/4$. Find the distribution of $S=X+Y$.

The PGFs are $$ G_X(s)=\frac12+\frac13s+\frac16s^2,\qquad G_Y(s)=\frac34+\frac14s^2. $$ Independence gives $$ G_S(s)=G_X(s)G_Y(s) =\left(\frac12+\frac13s+\frac16s^2\right) \left(\frac34+\frac14s^2\right). $$

Multiplying and collecting like powers, $$ G_S(s)=\frac38+\frac14s+\left(\frac18+\frac18\right)s^2 +\frac1{12}s^3+\frac1{24}s^4 =\frac38+\frac14s+\frac14s^2+\frac1{12}s^3+\frac1{24}s^4. $$ Thus $P(S=0)=3/8$, $P(S=1)=1/4$, $P(S=2)=1/4$, $P(S=3)=1/12$, and $P(S=4)=1/24$. The support is contained in $\{0,1,2,3,4\}$, since the smallest possible sum is $0+0$ and the largest is $2+2$. The probabilities check: $$ \frac38+\frac14+\frac14+\frac1{12}+\frac1{24} =\frac9{24}+\frac6{24}+\frac6{24}+\frac2{24}+\frac1{24}=1. $$

Coefficient Extraction with an Infinite Support

If a PGF has infinitely many terms, its product still determines each sum probability by a finite coefficient calculation: to obtain degree $k$, only degrees from $0$ through $k$ can contribute. A closed-form product may also make it possible to write the coefficients explicitly.

Worked Example: An Infinite-Support Sum with a Two-Point Shift

Let $X$ have $P(X=j)=2^{-(j+1)}$ for $j=0,1,2,\ldots$, and independently let $Y$ equal $0$ or $2$, each with probability $1/2$. Find $P(X+Y=k)$ for all $k\geq0$.

The probabilities for $X$ sum to one because $\sum_{j=0}^{\infty}2^{-(j+1)}=1$. Its PGF is the geometric series $$ G_X(s)=\sum_{j=0}^{\infty}2^{-(j+1)}s^j =\frac{1/2}{1-s/2}=\frac{1}{2-s},\qquad |s|<2. $$ Also $G_Y(s)=(1+s^2)/2$. Therefore $$ G_{X+Y}(s)=\frac{1+s^2}{2(2-s)} =\frac12(1+s^2)\sum_{j=0}^{\infty}\frac{s^j}{2^{j+1}}. $$

The coefficient of $s^k$ has one contribution from the $1$ term and, when $k\geq2$, another from the $s^2$ term: $$ P(X+Y=k)=\frac{1}{2^{k+2}}+ \begin{cases} 0,&k=0,1,\\[2pt] \frac{1}{2^k},&k\geq2. \end{cases} $$ Thus the first probabilities are $1/4$ at $k=0$, $1/8$ at $k=1$, and $5/16$ at $k=2$. For $k\geq2$, the expression simplifies to $5/2^{k+2}$. The support includes every nonnegative integer because $Y=0$ has positive probability and $X$ can equal any such integer. As a normalization check, $$ \frac14+\frac18+\sum_{k=2}^{\infty}\frac{5}{2^{k+2}} =\frac14+\frac18+\frac58=1. $$

Support Checks and Identifying a Candidate Law

For a discrete random variable, the support here means the set of integer values having positive probability. If $X$ and $Y$ have supports $A$ and $B$, respectively, then the support of their sum is $$ A+B=\{a+b:a\in A,\ b\in B\}. $$ Indeed, any such pair has positive joint probability by independence, so its sum has positive probability. Conversely, if a value $k$ is not such a sum, every term in the convolution for $P(X+Y=k)$ is zero. Support checks include simple bounds: if $X\geq m$ and $Y\geq r$ with probability one, then $X+Y\geq m+r$. They also detect gaps, such as parity restrictions.

A candidate PGF for a sum must satisfy several checks at once: its coefficients must be nonnegative, they must sum to one, and zero coefficients must be consistent with the possible sums. Matching a few initial coefficients is not enough to establish a distributional identity; the full coefficient sequence, or an exact equality of PGFs on $|s|<1$, is needed.

Worked Example: Rejecting a Candidate by Its Support

Suppose $X$ and $Y$ are independent, and each equals $0$ or $2$ with probability $1/2$ at each value. A proposed identification claims that $S=X+Y$ has PGF $(1+s)^2/4$. Check the claim and determine the correct PGF.

Each summand has PGF $(1+s^2)/2$, so the product rule gives $$ G_S(s)=\left(\frac{1+s^2}{2}\right)^2 =\frac14+\frac12s^2+\frac14s^4. $$ Hence $P(S=0)=1/4$, $P(S=2)=1/2$, and $P(S=4)=1/4$; all odd values have probability zero. This also follows from the support: adding two values from $\{0,2\}$ can only give $0,2,$ or $4$.

The proposed PGF expands as $$ \frac{(1+s)^2}{4}=\frac14+\frac12s+\frac14s^2. $$ It assigns positive probability to $1$ and has no probability at $4$, contradicting the support restriction and the computed coefficients. Its coefficients do sum to one, so normalization alone does not validate the claim. The correct PGF is $(1+s^2)^2/4$.

Why PGF Identification Works

The product theorem calculates the PGF of a sum, while uniqueness of coefficients turns that calculation into an identification of its distribution. The required uniqueness fact follows directly from the power-series representation.

Theorem: If $X$ and $Y$ are nonnegative integer-valued random variables and $G_X(s)=G_Y(s)$ for every real $s$ in an open interval containing $0$, then $P(X=k)=P(Y=k)$ for every $k\geq0$. Thus $X$ and $Y$ have the same distribution.

Proof. Both PGFs are power series converging for $|s|<1$. Equality on an open real interval containing $0$ implies that their derivatives of every order at $0$ are equal. For a PGF, termwise differentiation of a power series within its radius of convergence gives $$ G_X^{(k)}(0)=k!P(X=k),\qquad G_Y^{(k)}(0)=k!P(Y=k). $$ Equality of the derivatives therefore gives $P(X=k)=P(Y=k)$ for every nonnegative integer $k$, as required. $\square$

This theorem explains the logic of distribution identification: derive the sum's PGF using independence, then show that it agrees with the PGF of a proposed law. Alternatively, extract the coefficients directly and verify the resulting probabilities. In either route, the support and coefficient checks are essential safeguards against an algebraic mismatch.

Common Mistakes

Multiplying PGFs without independence. The product rule uses independence; in general, $E[s^Xs^Y]$ need not equal $E[s^X]E[s^Y]$.
Ignoring the index constraint in coefficient extraction. The coefficient at $s^k$ is a sum over pairs with indices adding to $k$, not a product of the two $k$th probabilities.
Accepting a formula because its coefficients sum to one. A normalized sequence can still put probability on values the sum cannot attain.
Checking only the smallest support value. Gaps matter too: if both summands are even-valued, their sum cannot be odd-valued.

Key takeaway: For independent nonnegative integer-valued variables, multiply their PGFs and extract coefficients to obtain the sum probabilities. Confirm that the coefficients form a probability distribution and that their support matches the possible sums.

Check Your Understanding

For each question, use the coefficient and support rules developed above.

If $G_X(s)=1/3+(2/3)s$ and $G_Y(s)=1/4+(3/4)s^2$ for independent variables, what is the coefficient of $s^2$ in $G_X(s)G_Y(s)$, and what probability does it represent?
Why does the coefficient of $s^k$ in a product of two PGFs involve only finitely many terms?
If $X$ takes only even nonnegative integer values and $Y$ takes only even nonnegative integer values, which values are ruled out from the support of $X+Y$?
What does $G_X(1)=1$ verify, and why does it not by itself confirm that a proposed PGF has the correct support?
State the independence condition needed to conclude $G_{X+Y}(s)=G_X(s)G_Y(s)$.