Probability Generating Functions, Practical Class 1.

7.1. Probability Generating Functions, Practical Class 1.#

AMSI 2026

A random variable $X$ takes values $0,1,2,3$ with probabilities

\[ p_0=0.2,\quad p_1=0.1,\quad p_2=0.4,\quad p_3=0.3. \]
1. Write down the probability generating function $\mu(x)$.
2. Using the notation $[x^k]f(x)$, express $p_k$ in terms of $\mu_X(x)$.
Let $f(x)=\sum_{n=0}^\infty a_n x^n$. Define $b_n=a_n+a_{n-1}$ for $n\ge1$, with $b_0=a_0$. Find a generating function for $(b_n)$ in terms of $f(x)$.
The PGF of a negative binomial random variable is

\[ \mu(x)=\left(\frac{1-p}{1-px}\right)^r. \]
1. Find $\mu(1)$. Explain why this is always the value for a PGF.
2. Differentiate $\mu(x)$ and evaluate at $x=1$. Explain why $\mu'(1)$ corresponds to the mean of the probability distribution.
Consider a distribution with $\mathbb{P}[X=n] = c/n!$ for $n=0, 1, 2, \ldots$ for a $c$ to be determined.
1. Find the PGF $\mu(x)$.
2. Find $\mu(1)$ and use this to determine what $c$ must be since this is a PGF.
3. Compare its algebraic form with the PGFs of the Poisson and geometric distributions.
4. Describe qualitatively how the probabilities $p_n$ behave as $n$ increases.
Use generating functions and $(1+x)^{2n}$ to prove

\[ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} \]

It may help to be reminded that $\binom{n}{k} = \binom{n}{n-k}$.
Show that if we assume $\binom{M}{N} = 0$ if $N>M$:

\[ \sum_{k=0}^\infty \binom{n-k}{k} = F_{n+1} \]
Let $f(x)=\sum_{n=0}^\infty F_n x^n$ be the Fibonacci generating function where $F_0=0$, $F_1=1$, and $F_{n+2}=F_n+F_{n+1}$.

\[ f(x) = \frac{x}{1-x-x^2} \]

and let

\[ g(x) = \frac{1}{1-x} \]
1. By writing $f(x)$ and $g(x)$ in series form, show that $f(x) g(x) = F_0 + (F_0+F_1)x + (F_0+F_1+F_2)x^2 + \cdots$.
2. Set $h(x) = \sum_{n=0}^\infty F_{n+2}x^n - \sum_{n=0}^\infty x^n$. Write the first sum in terms of $f(x)$, then use the expressions for $f(x)$ and $g(x)$ to rewrite $h(x)$ as a polynomial divided by a product of two polynomials. Compare with $f(x)g(x)$. What result about Fibonacci numbers does this prove?
Explain why the PGF of $X+Y$ is $\mu_X(x)\mu_Y(x)$ when $X$ and $Y$ are independent.
A biased die has probabilities proportional to $1,2,3,4,5,6$.
1. Find the PGF of one roll.
2. Find the PGF of the sum of two independent rolls.
3. Use the PGF to compute $\mathbb{P}(\text{sum}=7)$.
Let $\mu(x)=\sum_{k\ge0}p_k x^k$ be a PGF.
1. Show that
\[ \mu'(x)=\sum_{k\ge1}k p_k x^{k-1}. \]
1. Explain why evaluating $\mu'(1)$ corresponds to weighting probabilities by offspring number.
2. Compute $\mu'(1)$ and $\mu''(1)$ for a Poisson distribution and interpret both quantities.
Imagine a weighted coin with sides numbered $1$ and $2$, having a $2$ with probability $p_2$. Call the result $K$. After the flip, you roll $K$ (1 or 2) fair 4-sided dice numbered $1$, $2$, $3$, $4$ and sum the results.
1. Find the PGF of $K$ $\mu(x)$
2. For each of $K=1$ and $K=2$, find the PGF for the sum in terms of $\psi(x) = (x+x^2+x^3+x^4)/4$
3. Find the PGF of the sum of the combined process where $K=1$ or $K=2$ is possible.
4. Your result should equal $\mu(\psi(x))$. Explain why.
Assume that the offspring distribution of a Galton-Watson process has $\mu(x)$, but the probability of identifying any one of these offspring is only $0.6$.Using the fact from the previous question that a sum of a random number $K$ values of random numbers $Z$ has PGF equal to $\mu_K(\mu_Z(x))$, find the PGF for the number of offspring identified for an individual.
Let $\mu(x)$ be the PGF of the offspring distribution in a Galton-Watson process. Let $X_g$ be the population size in generation $g$.
1. Show that $$ \mathbb{E}[X_{g+1} | X_g] = X_g\,\mu'(1). $$
2. Deduce a formula for $\mathbb{E}[X_g]$ in terms of $\mu'(1)$.
Let $\alpha_g=\mathbb{P}(X_g=0)$.
1. Show that
\[ \alpha_{g+1} = \mu(\alpha_g), \]

where $\mu(x)$ is the offspring PGF.
1. Compute $q_1,q_2,q_3$ explicitly for a Bernoulli($p$) offspring distribution.
Let $R_0=\mu'(1)$.
1. Explain in words what the cases $R_0<1$, $R_0=1$, and $R_0>1$ represent for population growth.
2. Without computing extinction probabilities explicitly, explain why $R_0 \leq 1$ suggests eventual extinction is likely.