Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 36 · Random Variables Review

Generating Functions

Learn probability generating functions: definition, moments from derivatives, sums of independent variables and random sums, verified symbolically with SymPy.

A generating function packs an entire distribution into one function. It looks abstract at first, but it turns two painful operations into easy ones: finding moments (take derivatives) and adding independent random variables (multiply functions). Branching processes and random walks lean on it heavily.

The probability generating function

For a random variable N taking values 0, 1, 2, ..., the probability generating function (PGF) is

Text
G(s) = E[s^N] = p_0 + p_1 s + p_2 s² + p_3 s³ + ...      where p_k = P(N = k)

The coefficient of s^k is the probability p_k. The series converges at least for |s| <= 1.

Immediate facts:

  • G(1) = 1, because probabilities add to 1.
  • G(0) = p_0.
  • p_k = G^(k)(0) / k!: the distribution can be recovered from G.

Moments from derivatives

Differentiating term by term, G'(s) = Σ k p_k s^(k-1), so

Text
E[N] = G'(1)
E[N(N-1)] = G''(1)
Var(N) = G''(1) + G'(1) - (G'(1))²

Common PGFs

Distribution PGF G(s)
Bernoulli(p) 1 - p + p s
Binomial(n, p) (1 - p + p s)^n
Geometric(p) on 1, 2, ... p s / (1 - (1-p) s)
Poisson(λ) exp(λ(s - 1))

Let SymPy check the moment formulas for the Poisson case.

Python Moments of a Poisson variable from its PGF

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sums of independent variables

If X and Y are independent, then

Text
G_(X+Y)(s) = E[s^(X+Y)] = E[s^X] E[s^Y] = G_X(s) G_Y(s)

Multiplying PGFs adds the variables. This explains a pattern you already know: a Binomial(n, p) variable is a sum of n independent Bernoulli(p) variables, so its PGF is (1 - p + p s)^n. It also shows that the sum of independent Poissons is Poisson:

Text
exp(λ1 (s-1)) × exp(λ2 (s-1)) = exp((λ1 + λ2)(s-1))
Python Adding two dice by multiplying polynomials

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The coefficients of the product polynomial are exactly the probabilities of each total. This is the same as convolving the two distributions, but with a tidy algebraic wrapper.

Random sums

Let S = X_1 + ... + X_N where the X_i are i.i.d. non-negative integers with PGF G_X, and N is independent with PGF G_N. Conditioning on N:

Text
G_S(s) = E[ E[s^S | N] ] = E[ G_X(s)^N ] = G_N( G_X(s) )

A composition of PGFs! Differentiating at s = 1 by the chain rule gives E[S] = G_N'(1) G_X'(1) = E[N] E[X], matching the result from the previous lesson.

Python PGF of a random sum, checked by simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result is a famous fact called Poisson thinning: keep each point of a Poisson count independently with probability p, and the kept count is again Poisson, now with mean λp. You will meet it again for Poisson processes.

flowchart LR
    A["Distribution<br/>p_0, p_1, p_2, ..."] <-->|"coefficients"| B["PGF G(s)"]
    B --> C["Moments:<br/>G'(1), G''(1)"]
    B --> D["Sum of independent:<br/>multiply PGFs"]
    B --> E["Random sum:<br/>compose PGFs"]

What a generating function buys you.

Beyond PGFs

For variables that are not integer-valued, the analogous tools are the moment generating function M(t) = E[e^(tX)] and the characteristic function φ(t) = E[e^(itX)]. They share the key property: the transform of a sum of independent variables is the product of the transforms.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is G(1) for any PGF?

    G(1) = Σ p_k = 1, because the probabilities add to one.
  2. 2. How do you get E[N] from the PGF G?

    G'(s) = Σ k p_k s^(k-1), so G'(1) = Σ k p_k = E[N].
  3. 3. X and Y are independent with PGFs G_X and G_Y. The PGF of X + Y is...

    E[s^(X+Y)] = E[s^X] E[s^Y] by independence.
  4. 4. For a random sum S = X_1 + ... + X_N, the PGF of S is...

    Conditioning on N gives E[G_X(s)^N], which is G_N evaluated at G_X(s).

Summary

  • The PGF G(s) = E[s^N] stores P(N = k) as the coefficient of s^k.
  • E[N] = G'(1) and Var(N) = G''(1) + G'(1) - G'(1)².
  • Independent sums multiply PGFs; random sums compose them.
  • Binomial, Poisson and geometric PGFs have simple closed forms.

Next: Law of Large Numbers and the Central Limit Theorem