# Probability Generating Functions

The generating function associated with a sequence a_{0}, a_{1}, a_{2}, a_{3}, ... is a formal series

f(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ...

A random variable X that assumes integer values with probabilities P(X = n) = p_{n} is fully specified by the sequence p_{0}, p_{1}, p_{2}, p_{3}, ... The corresponding generating function

f(x) = p_{0} + p_{1}x + p_{2}x^{2} + p_{3}x^{3} + ...

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^{2} + (1/6)x^{3} + (1/6)x^{4} + (1/6)x^{5} + (1/6)x^{6}.

**Tossing two coins**. The sample space for a toss of two coins consists of four possible outcomes:

f(x) = (1/4)1 + (2/4)x + (1/4)x^{2}.

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^{2} = [(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 ^{3}.^{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^{2} + (1/6)x^{3} + (1/6)x^{4} + (1/6)x^{5} + (1/6)x^{6}. For two dice, we have

f^{2}(x) | = [(1/6)x + (1/6)x^{2} + (1/6)x^{3} + (1/6)x^{4} + (1/6)x^{5} + (1/6)x^{6}.]^{2} | |

= 6^{-2}[x^{2} + 2x^{3} + 3x^{4} + 4x^{5} + 5x^{6} + 6x^{7} + 5x^{8} + 4x^{9} + 3x^{10} + 2x^{11} + x^{12}], |

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.

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny