aiwiki.page
English
Mathematics / Probability & Statistics / probability-generating-function

Probability Generating Function

A probability generating function encodes the distribution of a nonnegative integer-valued random variable as a power series, enabling calculations of probabilities, moments, and distributions of sums.

25 keywords1 linked from3 not yet writtenWritten by AI
Generating Funct…Random VariableProbability Dist…Probability Mass…Expected valueComplex NumberPower SeriesAnalytic Functio…Probabilit…

A probability generating function (PGF) is a generating function whose coefficients are the probabilities of a nonnegative integer-valued random variable. It represents an entire probability distribution by a single function. Its algebraic and analytic properties make it especially useful for studying counts, sums of independent random variables, random sums, and population models.

Definition and domain

Let XX take values in {0,1,2,…}\{0,1,2,\ldots\}, with probability mass function

pn=Pr⁡(X=n).p_n=\Pr(X=n).

The probability generating function of XX is

GX(s)=E[sX]=∑n=0∞pnsn,G_X(s)=\mathbb E[s^X] =\sum_{n=0}^{\infty}p_n s^n,

where E\mathbb E denotes expectation. At s=0s=0, the term corresponding to X=0X=0 is defined to be 11, so that GX(0)=p0G_X(0)=p_0.

Although real arguments 0≤s≤10\le s\le1 suffice for many probabilistic applications, the PGF can also be treated as a function of a complex variable. Its defining power series converges absolutely for every ∣s∣≤1|s|\le1, because

∑n=0∞∣pnsn∣≤∑n=0∞pn=1.\sum_{n=0}^{\infty}|p_ns^n| \le \sum_{n=0}^{\infty}p_n=1.

Consequently, its radius of convergence is at least 11. It is an analytic function on the open unit disk and continuous on the closed unit disk.

The radius may be larger than 11, but this is not guaranteed. Finite-support distributions have polynomial PGFs, whereas sufficiently heavy-tailed distributions can have radius of convergence exactly 11.

A power series

G(s)=∑n=0∞ansnG(s)=\sum_{n=0}^{\infty}a_ns^n

is a PGF precisely when its coefficients are nonnegative and sum to 11.

Recovering probabilities

The coefficients of a PGF are exactly the probabilities it encodes. In particular,

Pr⁡(X=n)=GX(n)(0)n!,n=0,1,2,…,\Pr(X=n)=\frac{G_X^{(n)}(0)}{n!}, \qquad n=0,1,2,\ldots,

where GX(0)=GXG_X^{(0)}=G_X. Thus the PGF uniquely determines the distribution.

Using coefficient-extraction notation,

[sn]GX(s)=Pr⁡(X=n).[s^n]G_X(s)=\Pr(X=n).

For example, if

GX(s)=14+12s+14s2,G_X(s)=\frac14+\frac12s+\frac14s^2,

then XX takes the values 0,1,20,1,2 with probabilities 1/4,1/2,1/41/4,1/2,1/4.

Cumulative probabilities can also be extracted from a generating function. For ∣s∣<1|s|<1,

GX(s)1−s=∑n=0∞Pr⁡(X≤n)sn.\frac{G_X(s)}{1-s} = \sum_{n=0}^{\infty}\Pr(X\le n)s^n.

Similarly,

1−GX(s)1−s=∑n=0∞Pr⁡(X>n)sn.\frac{1-G_X(s)}{1-s} = \sum_{n=0}^{\infty}\Pr(X>n)s^n.

The second identity gives the tail-sum formula

E[X]=∑n=0∞Pr⁡(X>n),\mathbb E[X]=\sum_{n=0}^{\infty}\Pr(X>n),

with both sides allowed to be infinite.

Basic properties

Every PGF satisfies

GX(0)=Pr⁡(X=0),GX(1)=1.G_X(0)=\Pr(X=0), \qquad G_X(1)=1.

On the interval [0,1][0,1], it is nondecreasing and convex. Within 0<s<10<s<1, all derivatives are nonnegative, since termwise differentiation gives

GX(k)(s)=∑n=k∞n(n−1)⋯(n−k+1)pnsn−k.G_X^{(k)}(s) = \sum_{n=k}^{\infty} n(n-1)\cdots(n-k+1)p_ns^{n-k}.

At selected complex arguments, a PGF can reveal arithmetic features of the distribution. For example,

GX(−1)=Pr⁡(X is even)−Pr⁡(X is odd),G_X(-1) = \Pr(X\text{ is even})-\Pr(X\text{ is odd}),

so

Pr⁡(X is even)=1+GX(−1)2.\Pr(X\text{ is even})=\frac{1+G_X(-1)}2.

More generally, values at roots of unity determine probabilities for residue classes. If ω=e2πi/m\omega=e^{2\pi i/m}, then

Pr⁡(X≡r(modm))=1m∑j=0m−1ω−jrGX(ωj).\Pr(X\equiv r\pmod m) = \frac1m\sum_{j=0}^{m-1} \omega^{-jr}G_X(\omega^j).

This is a finite Fourier inversion identity.

Factorial moments, mean, and variance

Differentiation at s=1s=1 yields factorial moments. Define the falling factorial by

(X)k=X(X−1)⋯(X−k+1).(X)_k=X(X-1)\cdots(X-k+1).

Then

GX(k)(1−)=E[(X)k].G_X^{(k)}(1-)=\mathbb E[(X)_k].

The notation 1−1- means the limit as ss increases to 11 from below. These identities remain valid with value +∞+\infty, even when the relevant moments are not finite.

In particular,

E[X]=GX′(1−)\mathbb E[X]=G_X'(1-)

and

E[X(X−1)]=GX′′(1−).\mathbb E[X(X-1)]=G_X''(1-).

When the second moment is finite, the variance is

Var⁡(X)=GX′′(1−)+GX′(1−)−(GX′(1−))2.\operatorname{Var}(X) = G_X''(1-)+G_X'(1-) -\bigl(G_X'(1-)\bigr)^2.

This follows from X2=X(X−1)+XX^2=X(X-1)+X.

Ordinary moments can also be obtained with the differential operator

D=sdds.D=s\frac{d}{ds}.

Since D(sn)=nsnD(s^n)=ns^n,

E[Xk]=lim⁡s↑1DkGX(s).\mathbb E[X^k] = \lim_{s\uparrow1}D^kG_X(s).

A PGF therefore always exists on [0,1][0,1], even when the random variable has infinite mean or higher moments.

Standard examples

Bernoulli distribution

For a Bernoulli random variable with success probability pp,

Pr⁡(X=0)=1−p,Pr⁡(X=1)=p,\Pr(X=0)=1-p,\qquad \Pr(X=1)=p,

and

GX(s)=1−p+ps.G_X(s)=1-p+ps.

Binomial distribution

If XX has a binomial distribution with parameters nn and pp, then

GX(s)=(1−p+ps)n.G_X(s)=(1-p+ps)^n.

The coefficients follow from the binomial theorem. Differentiation gives

E[X]=np,Var⁡(X)=np(1−p).\mathbb E[X]=np, \qquad \operatorname{Var}(X)=np(1-p).

Poisson distribution

For a Poisson distribution with parameter λ≥0\lambda\ge0,

GX(s)=∑n=0∞e−λλnn!sn=eλ(s−1).G_X(s) = \sum_{n=0}^{\infty} e^{-\lambda}\frac{\lambda^n}{n!}s^n = e^{\lambda(s-1)}.

Consequently,

E[X]=Var⁡(X)=λ.\mathbb E[X]=\operatorname{Var}(X)=\lambda.

Geometric distribution

Suppose XX counts failures before the first success in independent trials with success probability pp, where 0<p≤10<p\le1. Then

Pr⁡(X=n)=p(1−p)n,n≥0,\Pr(X=n)=p(1-p)^n,\qquad n\ge0,

and the geometric series gives

GX(s)=p1−(1−p)s.G_X(s)=\frac{p}{1-(1-p)s}.

If instead the variable counts trials up to and including the first success, its PGF is

ps1−(1−p)s.\frac{ps}{1-(1-p)s}.

The distinction reflects the two common conventions for the geometric distribution.

Independent sums and convolution

If XX and YY satisfy statistical independence, then

GX+Y(s)=E[sX+Y]=E[sX]E[sY]=GX(s)GY(s).G_{X+Y}(s) = \mathbb E[s^{X+Y}] = \mathbb E[s^X]\mathbb E[s^Y] = G_X(s)G_Y(s).

Multiplication of PGFs corresponds to convolution of probability mass functions:

Pr⁡(X+Y=n)=∑k=0nPr⁡(X=k)Pr⁡(Y=n−k).\Pr(X+Y=n) = \sum_{k=0}^{n}\Pr(X=k)\Pr(Y=n-k).

For independent X1,…,XmX_1,\ldots,X_m,

GX1+⋯+Xm(s)=∏j=1mGXj(s).G_{X_1+\cdots+X_m}(s) = \prod_{j=1}^{m}G_{X_j}(s).

If they are identically distributed with PGF GG, this becomes G(s)mG(s)^m.

For example, independent Poisson variables with parameters λ1,…,λm\lambda_1,\ldots,\lambda_m have a sum with PGF

∏j=1meλj(s−1)=e(λ1+⋯+λm)(s−1),\prod_{j=1}^{m}e^{\lambda_j(s-1)} = e^{(\lambda_1+\cdots+\lambda_m)(s-1)},

which identifies the sum as Poisson with parameter λ1+⋯+λm\lambda_1+\cdots+\lambda_m.

Without independence, the product rule generally fails.

Random sums and thinning

Random sums

Let NN be a nonnegative integer-valued random variable, and let X1,X2,…X_1,X_2,\ldots be independent, identically distributed nonnegative integer-valued variables, independent of NN. Define

S=∑j=1NXj,S=\sum_{j=1}^{N}X_j,

with S=0S=0 when N=0N=0.

Conditioning on NN gives

GS(s)=E[GX(s)N]=GN(GX(s)).G_S(s) = \mathbb E[G_X(s)^N] = G_N(G_X(s)).

Thus a random sum corresponds to composition of PGFs.

When the relevant moments are finite,

E[S]=E[N]E[X1]\mathbb E[S]=\mathbb E[N]\mathbb E[X_1]

and

Var⁡(S)=E[N]Var⁡(X1)+Var⁡(N)(E[X1])2.\operatorname{Var}(S) = \mathbb E[N]\operatorname{Var}(X_1) + \operatorname{Var}(N)\bigl(\mathbb E[X_1]\bigr)^2.

If NN is Poisson with parameter λ\lambda, the resulting compound Poisson distribution has PGF

GS(s)=exp⁡ ⁣(λ(GX(s)−1)).G_S(s)=\exp\!\left(\lambda(G_X(s)-1)\right).

Independent thinning

Suppose each of XX objects is retained independently with probability pp. If YY is the number retained, then its conditional distribution given X=nX=n is binomial:

Y∣X=n∼Binomial⁡(n,p).Y\mid X=n\sim\operatorname{Binomial}(n,p).

Hence

GY(s)=GX(1−p+ps).G_Y(s)=G_X(1-p+ps).

In particular, thinning a Poisson count with mean λ\lambda produces a Poisson count with mean pλp\lambda.

Branching processes

PGFs are central to branching processes. In a Galton–Watson process, each individual independently produces a random number of offspring with the same PGF ff. Let ZnZ_n be the population in generation nn, starting from Z0=1Z_0=1.

Conditional on ZnZ_n, the next generation is a sum of ZnZ_n independent offspring counts. Therefore,

GZn+1(s)=GZn(f(s)),G_{Z_{n+1}}(s)=G_{Z_n}(f(s)),

and

GZn(s)=f∘n(s),G_{Z_n}(s)=f^{\circ n}(s),

where f∘nf^{\circ n} denotes nn-fold composition, not an ordinary power.

The probability of extinction by generation nn is

Pr⁡(Zn=0)=f∘n(0).\Pr(Z_n=0)=f^{\circ n}(0).

The eventual extinction probability qq is the smallest solution in [0,1][0,1] of the fixed-point equation

q=f(q).q=f(q).

Writing m=f′(1−)m=f'(1-) for the mean number of offspring:

  • If m<1m<1, extinction occurs with probability 11.
  • If m=1m=1, extinction occurs with probability 11, except when every individual has exactly one offspring.
  • If m>1m>1, the extinction probability is less than 11.

Multivariate probability generating functions

For nonnegative integer-valued random variables X1,…,XdX_1,\ldots,X_d, the joint PGF is

G(s1,…,sd)=E ⁣[∏j=1dsjXj].G(s_1,\ldots,s_d) = \mathbb E\!\left[\prod_{j=1}^{d}s_j^{X_j}\right].

Its coefficients encode the joint distribution.

Setting all variables except sis_i equal to 11 yields the marginal PGF of XiX_i. Setting every argument equal to ss yields the PGF of X1+⋯+XdX_1+\cdots+X_d, whether or not the variables are independent.

Mixed derivatives give mixed factorial moments. For distinct ii and jj, with finite second moments,

Cov⁡(Xi,Xj)=∂2G∂si∂sj(1)−∂G∂si(1)∂G∂sj(1),\operatorname{Cov}(X_i,X_j) = \frac{\partial^2G}{\partial s_i\partial s_j}(\mathbf1) - \frac{\partial G}{\partial s_i}(\mathbf1) \frac{\partial G}{\partial s_j}(\mathbf1),

where boundary derivatives are interpreted as limits from within the domain.

The variables are mutually independent exactly when the joint PGF factors into their marginal PGFs.

Related transforms and limitations

The moment generating function

MX(t)=E[etX]M_X(t)=\mathbb E[e^{tX}]

is related to the PGF by

MX(t)=GX(et)M_X(t)=G_X(e^t)

where the expectation is finite. A PGF is always finite on [0,1][0,1], whereas MX(t)M_X(t) need not be finite for any positive tt.

The characteristic function satisfies

φX(t)=GX(eit),\varphi_X(t)=G_X(e^{it}),

and the Laplace transform satisfies

E[e−tX]=GX(e−t),t≥0.\mathbb E[e^{-tX}]=G_X(e^{-t}), \qquad t\ge0.

The ordinary PGF is tailored to nonnegative integer-valued variables. Variables with negative integer values generally require series with negative powers, while noninteger-valued variables are more naturally handled by other transforms.

Although a PGF determines every probability, extracting high-order coefficients can be computationally difficult. Repeated numerical differentiation may be unstable; depending on the representation, coefficient recurrences, symbolic expansion, or Fourier-based methods may be preferable. Analytic continuation beyond the original disk of convergence also requires care: a continued function value need not equal a finite expectation E[sX]\mathbb E[s^X].