Probability Generating Functions

The generating function associated with a sequence a₀, a₁, a₂, a₃, ... is a formal series

f(x) = a₀ + a₁x + a₂x² + a₃x³ + ...

A random variable X that assumes integer values with probabilities P(X = n) = p_n is fully specified by the sequence p₀, p₁, p₂, p₃, ... The corresponding generating function

f(x) = p₀ + p₁x + p₂x² + p₃x³ + ...

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)x² + (1/6)x³ + (1/6)x⁴ + (1/6)x⁵ + (1/6)x⁶.

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)x².

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)x² = [(1/2) + (1/2)x]².

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]³. 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)x² + (1/6)x³ + (1/6)x⁴ + (1/6)x⁵ + (1/6)x⁶. For two dice, we have

	f²(x)	= [(1/6)x + (1/6)x² + (1/6)x³ + (1/6)x⁴ + (1/6)x⁵ + (1/6)x⁶.]²
		= 6^-2[x² + 2x³ + 3x⁴ + 4x⁵ + 5x⁶ + 6x⁷ + 5x⁸ + 4x⁹ + 3x¹⁰ + 2x¹¹ + x¹²],

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.

71536884