Probability Generating Function Of The Sum Of Independent Random Variables

1. Core Concept Overview & Intuition

The probability generating function (p.g.f.) is a transform that encodes the entire probability mass function of a non-negative integer-valued random variable into a single power series. Its most striking structural property is that it converts the operation of adding independent random variables into the operation of multiplying their generating functions. This is the central idea of the present unit.

Intuitively, if $X$ and $Y$ are independent, then the event ${X+Y=j}$ is assembled from all pairs $(i,k)$ with $i+k=j$, and independence makes the joint probability factor as a product. When these products are summed against $s^{j}$, the double sum factorises into the product of two separate series. The p.g.f. therefore acts as a "multiplicative bookkeeper" for sums of independent variables.

Two distinct situations must be distinguished:

• A fixed number $n$ of independent terms, giving $S_{n}=X_{1}+X_{2}+\cdots+X_{n}$.
• A random number $N$ of independent terms, giving $S_{N}=X_{1}+X_{2}+\cdots+X_{N}$, where $N$ is itself a random variable independent of the $X_{i}$.

The first case leads to the product rule for p.g.f.s and to the classical closure results (sums of independent Poisson variables are Poisson; sums of independent Bernoulli variables are binomial). The second case leads to the compounding formula $H(s)=G(P(s))$, in which the p.g.f. of the random count $N$ is composed with the p.g.f. of a single term.

A useful mental picture is that of a two-stage random experiment: first a random number $N$ of "trials" is drawn, then each trial independently contributes a random amount $X_{i}$. The compounding formula captures this hierarchy exactly, and differentiating it at $s=1$ yields the mean and variance relations that are the practical payoff of the theory.

2. Mathematical Formalization & Core Definitions

> Definition (Probability Generating Function). Let $X$ be a random variable taking values in ${0,1,2,\dots}$ with probability mass function $p_{k}=\Pr(X=k)$. The probability generating function of $X$ is the power series

$$
P(s)=\sum_{k=0}^{\infty}p_{k}s^{k},
$$

> defined for those $s$ for which the series converges; in particular it converges absolutely for $\lvert s\rvert\le 1$.

> Definition (Tail Probabilities). For a non-negative integer-valued random variable $X$ with mass function $p_{k}$, the upper tail probabilities are

$$
q_{k}=\Pr(X>k)=p_{k+1}+p_{k+2}+p_{k+3}+\cdots,
$$

> and the lower tail (cumulative) probabilities are

$$
q_{k}=\Pr(X\le k)=p_{k}+p_{k-1}+p_{k-2}+\cdots+p_{1}+p_{0}.
$$

The tail sequences satisfy simple recursion relations that are used repeatedly. For the upper tail, $q_{k}=p_{k+1}+q_{k+1}$, and in particular $q_{0}=p_{1}+p_{2}+p_{3}+\cdots$. Since $p_{0}+q_{0}=p_{0}+p_{1}+p_{2}+\cdots=1$, we have the normalisation $\sum_{k}p_{k}=1$. For the lower tail, $q_{k}-q_{k-1}=p_{k}$ for $k\ge 1$, and $p_{0}=q_{0}$.

> Definition (Independence). Random variables $X_{1},\dots,X_{n}$ are mutually independent if for every choice of values $k_{1},\dots,k_{n}$,

$$
\Pr(X_{1}=k_{1},\dots,X_{n}=k_{n})=\prod_{i=1}^{n}\Pr(X_{i}=k_{i}).
$$

> Definition (Identically Distributed). The variables $X_{1},\dots,X_{n}$ are identically distributed if they share a common mass function $p_{k}=\Pr(X_{i}=k)$ and hence a common p.g.f. $P(s)$.

> Definition (Compound Poisson Distribution). A distribution whose generating function has the form

$$
H(s)=e^{-\lambda\left(1-P(s)\right)},
$$

> where $P(s)$ is itself a probability generating function and $\lambda>0$, is called a compound Poisson distribution.