# Probability Generating Functions

The generating function associated with a sequence a0, a1, a2, a3, ... is a formal series

f(x) = a0 + a1x + a2x2 + a3x3 + ...

A random variable X that assumes integer values with probabilities P(X = n) = pn is fully specified by the sequence p0, p1, p2, p3, ... The corresponding generating function

f(x) = p0 + p1x + p2x2 + p3x3 + ...

is commonly referred to as a probability generating function. Each term is a power of x with a coefficient; the exponent points to a value that the random value may take; the coefficient indicates the probability of the random variable taking the value in the exponent.

### Examples

Tossing a coin. Let's write 0 for the "heads" even, 1 for "tails". The generating function of the experiment that consists of a single toss of a coin is then f(x) = (1/2) + (1/2)x. One possible interpretation is that, in a single toss of a coin, the probability of having 0 heads is 1/2; the probability of having 1 heads is also 1/2.

Rolling a die. The generating function for the experiment of rolling a die once is

f(x) = (1/6)x + (1/6)x2 + (1/6)x3 + (1/6)x4 + (1/6)x5 + (1/6)x6.

Tossing two coins. The sample space for a toss of two coins consists of four possible outcomes: {HH, HT, TH, TT}, or, if we use the convention of denoting the events H and T as 0 and 1, {00, 01, 10, 11}. There is a convenience in the switch of the notations if we are interested in the number of time "heads" showed up in two tosses. It is 0 in the first event, 1 = 0 + 1, in the next two, and 2 in the last 11 event. It follows that the probabilities of having 0, 1, or 2 heads in two coin tosses are 1/4, 2/4, and 1/4, respectively. The probability generating function for the random number of heads in two throws is defined as

f(x) = (1/4)1 + (2/4)x + (1/4)x2.

Observe that the generating function of two coin tosses equals to the square of of the generating function associated with a single toss.

(1/4)1 + (2/4)x + (1/4)x2 = [(1/2) + (1/2)x]2.

The possible outcomes for three coins are {000, 001, 010, 011, 100, 101, 110, 111}. If we are only concerned with the number of heads shown in three throws, then the sample space is {0, 1, 2, 3}, with probabilities 1/8, 3/8, 3/8, 1/8. This coefficients also come from the binomial theorem for [(1/2) + (1/2)x]3. This is a general rule, the generating function for the number of heads shown in N coin tosses equals [(1/2) + (1/2)x]N = 2-N(1 + x)N.

Even more generally, if f(x) and g(x) are the probability generating functions of two independent random variables X and Y, then the generating function, corresponding to the sum X + Y equals the product f(x)g(x)!

Rolling two dice. For a single die, f(x) = (1/6)x + (1/6)x2 + (1/6)x3 + (1/6)x4 + (1/6)x5 + (1/6)x6. For two dice, we have

 f2(x) = [(1/6)x + (1/6)x2 + (1/6)x3 + (1/6)x4 + (1/6)x5 + (1/6)x6.]2 = 6-2[x2 + 2x3 + 3x4 + 4x5 + 5x6 + 6x7 + 5x8 + 4x9 + 3x10 + 2x11 + x12],

which tells us that, for example, there are 5 ways to get 6 in two throws. Indeed,

6 = 1 + 5 = 2 + 4 = 3 + 3 = 4 + 2 = 5 + 1.

This happens with the probability of 5/36.  