Generating function

Short for "Probabilitiy generating function". Not to be confused with the "Moment generating function (mgf)".

-----

Let X be a random variable with known probability density or mass function f_X (.). This function contains all the information about X, and therefore one could imagine that any question asked about X can be answered by making appropriate calculations on  f_X (.).

Yet, just because f_X (.) is known does not mean that extracting information from it is easy as calculations have an unfortunate tendency to be intractable. A powerful strategy for overcoming this problem is then to use not  f_X (.) itself, but a transform of f_X (.) which will lend itself to some kind of calculation leading to the desired result. The most popular transforms are the moment generating function, used many times throughout this site, and its complex numbers version, the characteristic function (not addressed in this site).

-----

In the special case where X is a non-negative integer-valued random variable (e.g binomial, geometric, Poisson...), another transform comes in handy : the (probability) generating function.

Definition of the generating function

So let X be a non-negative integer-valued random variable with probability mass function f_X (k) :

f_X (k) = : P{X = k} = p_k

By definition, the generating function G(s) associated to f_X (k) (or, by an abuse of language, "associated to X") is :

So the generating function is just the power series whose coefficients are the p_ks.

Note that, by definition of the expectation, this expression can also be written :

G(s) = E[s^X]

We use the generating function within the context of Probability theory, but, more generally, the generating function of an infinite sequence of positive real numbers is defined as above even if the infinite sum of these numbers is not 1.

Properties of the generating function

Existence

The first question is of course whether such a definition makes sense.

Make s = 1 in the above infinite series. We then have

G(1) = Σ_k p_k = 1               k = 0, 1, 2...

The series therefore converges for s = 1, and from the theory of power series, it also converges for all s < 1. The radius of convergence of the series is therefore at least 1.

So, contrary to the moment generating function, the generating function always exists.

Differentiation

We'll show that a generating function is :

    * Monotonically increasing in s (obvious).

    * Continuous on [0, 1) (note that 1 is excluded from the result).

    * Infinitely differentiable in [0, 1) and then :

Although these results can be derived from the larger framework of the theory of power series, we'll give more elementary but also more direct demonstrations.

Generating probabilities

We'll show that :

If G(s) is known as a power series expansion in s, then p_n is just the coefficient of sⁿ in this expansion.

------

Hence, when the generating function of f_X (.) is known, there is an explicit procedure for retrieving P{X = n} for all values of n. This is in sharp constrast with the moment generating function, which cannot be "inverted".

We'll use this property for calculating the probability mass function of the Poisson distribution.

Uniqueness

From the above result, it appears clearly that two different generating functions can only be associated to two different probability mass functions, a property also shared by the mgf.

Factorial moments

We'll show that  :

The quantity on the RHS of this equation is called a "factorial moment". So differentiating the gf does not lead directly to moments (as differenting the mgf does), but to another sort of "moments", from which ordinary moments can be derived (although this derivation is convenient only for low order moments).

We see that :

    * The mean is obtained for n = 1.

    * E[X(X - 1)] is obtained for n = 2. In the Tutorial, we'll see that the variance can easily be obtained from the expectation and the second order factorial moment.

_______________

The thorny point about this result is that although we know that G(s) exists for s = 1 and has derivatives of all orders for s < 1, we cannot guarantee that it exists for s > 1, and therefore can be differentiated in s = 1. This is the reason why we have to use the "left derivative" of G(s) instead of just the derivative.

If G(s) exists for s > 1, then the "lim" part can be dispensed with.

Generating function and Convolution

The most direct way of obtaining the distribution of the sum of two independent random variables is to calculate the convolution of the probability distribution functions of these two r.v.s. Yet, the calculations often prove cumbersome, and the mgf may then be of great help.

In the case of two independent non-negative integer-valued r.v.s, calling on the generating functions of these two variables often proves to be even more convenient.

We'll show that :

    * If the generating function of X₁ is G₁(s),

    * And the generating function of X₂ is G₂(s),

    * X₁ and X₂ are independent,

then the generating function of (X₁ + X₂ ) is the product of their generating functions .

This result is similar to that obtained with moment generating functions.

-----

This result generalizes straightforwardly to the case of any number of variables.

Random sums

This result can be further generalized to the case where the number N of variables in the sum is itself a random variable.

Consider an infinite sequence {X⁽ⁿ⁾, n = 1, 2,  ...} of iid non-negative integer-valued random variables, and denote G_X (s) their common generating function.

Let also N be another non-negative integer-valued random variable independent of {X⁽ⁿ⁾}. Denote G_N (.) is generating function.

We now build a new r.v. Y as follows :

    * A value n is drawn form N.

    * We then draw realizations of the first n X⁽ⁿ⁾ and add the values of these realizations.

    * The result is considered as a realization of Y.

More formally, Y is defined as

with N a r.v. as explained above.

-----

Denote G_Y (.) the generating function of Y. We'll show that

This result is fundamental for studying a certain class of stochatic processes known as "branching processes" (not addressed in this Glossary).

-----

We'll also show that

a result that we already obtained here in more general context by calling on the properties of the iterated expectation.

Limit distributions and the continuity theorem

Again, in what follows, we consider only non-negative integer-valued random variables.

Consider an infinite sequence {X⁽ⁿ⁾, n = 1, 2,  ...}of such variables. The probability mass function of the n^th variable of the sequence is denoted

P{X⁽ⁿ⁾ = k} = p_k⁽ⁿ⁾

and its generating function is denoted G_n(s).

We assume that for any k, the sequence {p_k⁽ⁿ⁾} converges to a value p_k. as n → ∞.

We'll show that then the corresponding sequence {G_n(s)} converges to a limit function G(s) that will turn out to be the generating function of the limit sequence {p_k}.

Although  Σ_k p_k⁽ⁿ⁾ = 1 for any n, it is not clear that the same should be true for the sequence {p_k} of limit values, and it is indeed not always the case. This is why the "X" of the above illustration is followed by question marks. The sequence {p_k} is the pmf of some rv X if and only if G(1) = 1.

-----

Conversely, we'll show that if the sequence of generating function {G_n(s)} converges to a limit function G(s), then G(s) is the generating function of a sequence of {p_k}, and that for all k, {p_k⁽ⁿ⁾} converges to p_k as n grows without limit.

Again, {p_k} will be a pmf if and only if G(1) = 1.

______

We'll use this result for calculating the generating function of the Poisson distribution as the limit of the generating function of the binomial distribution.

_____________________________________________________________

In this Tutorial, we first give some examples of generating functions (Poisson, binomial and geometric distributions).

We then show that a generating function is continuous, and can be infinitely differentiated. Although these results are immediate consequences of the theory of power series, we'll give elementary and direct demonstrations.

    * A first consequence of infinite differentiability will be that the probability mass fuction (of a non-negative integer-valued rv) can be retrieved from its generating function, a fact that has no equivalent with the moment generating function.

Consequently, il will appear that the generating function enjoys the uniqueness property (just as the mgf does) : two rvs have identical generating functions if and only if they have identical probability mass functions.

* A second consequence of infinite differentiability will be that generating functions can be used for calculating so-called "factorial moments". Although it is theoretically possible to derive moments from factorial moments, the calculation is practical only for low order moments, and in particular we'll show how the variance can be derived from the first two factorial moments.

We'll then use these results for calculating the mean and variance of the distributions already mentioned.

GENERATING FUNCTIONS

______________________________________________________

In this Tutorial, we show that the generating function of the sum of independent random variables is the product of their generating functions.

We then review some examples, of which the sum of iid geometric variables will be the only one presenting some difficulty.

These examples will show that using the properties of generating functions can be more convenient than convolution for calculating the pmf of a sum of rv.

GENERATING FUNCTION OF THE SUM

OF INDEPENDENT RANDOM VARIABLES

____________________________________________________

We establish the generating function of a sum of iid non-negative integer-valued random variables, but with the number of variables in the sum being itself a random variable. The distribution of this random sum is known as a compound distribution.

We'll then see that when the compounding rv is Poisson distributed, the result takes a special form useful in many applications.

We calculate the expectation of a random sum, and thus obtain, in the special case of non-negative integer-valued rv a result that we already obtained here in a more general context.

We finally give an example of compounding that leads to the concept of "thinning" or "splitting" of a Poisson process.

GENERATING FUNCTION OF A RANDOM SUM

_______________________________________________

In this Tutorial, we address one of the most important applications of generating functions.

    * We first show that if a sequence of probability mass functions converges to a limit, then the coresponding sequence of generating functions converges to a limit function which is the generating function of the limit sequence of pmfs.

    * We then show the converse : if a sequence of generating functions converges to a limit function, then the corresponding sequence of pmfs converges to a limit sequence whose generating function is the limit of the sequence of generating functions. Proving this result will lead us to make a little refreshing detour to visit some elementary (and also some not so elementary) results of general topology.

LIMIT DISTRIBUTIONS AND

THE CONTINUITY THEOREM

____________________________________________________

Related readings :