1.4. Generating Function Examples

Example 1.1 (Geometric Sequences)

Consider the generating function for the sequence \(1, 1, 1, 1, \ldots\). It is given by \(f(x) = 1 + x + x^2 + \cdots\)

\[ f(x) = 1 + x + x^2 + \cdots \]

If you remember the formula for a geometric series, this can be written in compact form:

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

This converges for \(|x|<1\).

Remark 1.3

The example above used \(1 + x + \cdots = 1/(1-x)\) for \(|x|<1\). If you don’t remember this formula for the geometric series, here is a derivation. Define \(f_N(x) = 1 + x + x^2 + \cdots + x^N\). Multiply it by \(1-x\):

\[\begin{align*} f_N(x)(1-x) &= f_N(x) - x f_N(x)\\ &= (1 + x + x^2 +\cdots +x^N ) - (x + x^2 + \cdots + x_N + x^{N+1})\\ &= 1-x^{N+1} \end{align*}\]

So \(f_N(x) = (1-x^{N+1})/(1-x)\). Assuming \(|x|<1\), then taking \(N \to \infty\) gives \(f(x) = \lim_N \to \infty f_N(x) = 1/(1-x)\)

In the self-test below, you will show that \(f(x) = A/(1-rx)\) is the generating function for the sequence \(A, Ar, Ar^2, \ldots\).

Example 1.2 (The Binomial Coefficients)

Consider the binomial coefficients for a fixed integer \(N\) and integer values of \(k\):

\[\begin{split} \binom{N}{k} = \begin{cases} \frac{N!}{k!(N-k)!} & k=0, \ldots, N\\ 0 & k<0 \text{ or } k>N \end{cases} \end{split}\]

The generating function

\[ f(x) = \binom{N}{0}x^0 + \binom{N}{1}x^1 + \cdots = \sum_k \binom{N}{k} x^k \]

is

\[f(x) = (1+x)^N\]

Example 1.3 (Binomial Expansion)

Consider \((1+x)^r\) where \(r\) may not be an integer. Then

\[ (1+x)^r = 1 + rx + \frac{r(r-1)}{2!} x^2 + \frac{r(r-1)(r-2)}{3!}x^3 + \cdots + \frac{r(r-1)\cdots(r-n+1)}{n!} x^n + \cdots \]

So the generating function of \(1, r, r(r-1)/2, r(r-1)(r-2)/3!, \ldots\) is \((1+x)^r\).

Example 1.4 (The Fibonacci sequence)

Consider the Fibonacci sequence defined by \(F_0=0\), \(F_1 = 1\) and \(F_{n} = F_{n-1}+ F_{n-2}\) for \(n \geq 2\). Given this sequence of numbers, we can define the generating function of the Fibonacci sequence:

\[\begin{align*} f(x) &= F_0 + F_1 x + F_2 x^2 + F_3 x^3 + F_4x^4+F_5x^5+F_6x^6+\cdots \\ &= 0 + 1x + 1x^2 + 2x^3 + 3 x^4 +5x^5 + 8x^6+\cdots \end{align*}\]

Let’s try to write this as a compact expression. We need to use \(F_n = F_{n-1}+ F_{n-2}\) to figure out what \(f(x)\) is. We start with the definition of a generating function, and then we use properties of the Fibonacci sequence.

\[\begin{align*} f(x) &= F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \ldots \\ &= F_0 + F_1 x + \sum_{n=2}^\infty F_nx^n\\ &= F_0 + F_1 x + \sum_{n=2}^\infty (F_{n-1} + F_{n-2})x^n\\ &= F_0 + F_1 x + \sum_{n=2}^\infty F_{n-2}x^n + \sum_{n=2}^\infty F_{n-1}x^n\\ &= F_0 + F_1 x + x^2 \sum_{n=2}^\infty F_{n-2}x^{n-2} + x \sum_{n=2}^\infty F_{n-1} x^{n-1}\\ &= F_0 + F_1 x + x^2 (F_0 + F_1x + F_2 x^2+\cdots) + x (F_1x + F_2 x^2 + \cdots)\\ &= F_0 + F_1x + x^2f(x) + x (f(x)-F_0)\\ &= x + (x+x^2)f(x) \end{align*}\]

using \(F_0=0\) and \(F_1=1\) for the last step, and the definition of \(f(x)\) for the next to last step.

Moving the terms with \(f(x)\) onto the left hand side:

\[\begin{align*} f(x) ( 1- x - x^2) &= x\\ \Rightarrow f(x) &= \frac{ x}{1-x-x^2} \end{align*}\]

The self-test will use the generating function of the Fibonacci sequence to derive a formula for each term.

1.4.1. Probability Generating Functions

We now look specifically at a few probability generating functions.

Example 1.5 (Flipping a fair coin)

Consider a fair coin. We will set \(n\) to be the number of heads from a single flip. Then \(p_0 =1/2\) and \(p_1 = 1/2\) and \(p_n = 0\) for \(n\geq 2\).

Because this is a probabiity distribution for \(0,1\), the resulting generating function is a probability generating function (PGF):

\[ \mu(x) = \frac{1+x}{2} \]

Example 1.6 (Flipping a weighted coin)

Now consider a coin with probaibility \(p_H\) of heads and \(1-p_H\) of tails. Again, we count the number of heads, so \(p_0=1-p_H\) and \(p_1 = p_H\)

Then the PGF is

\[ \mu(x) = (1-p_H) + p_H x \]

Example 1.7 (6-sided dice)

Consider the probability of rolling a \(k\) with a typical 6-sided die, for which \(p_k = 1/6\) for \(k=1, 2, \ldots, 6\).

The PGF is:

\[\begin{align*} \mu(x) &= \frac{1}{6}x + \frac{1}{6}x^2 + \ldots + \frac{1}{6} x^6\\ &= \frac{1}{6} (x + x^2 + x^3 + x^4 + x^5 + x^6) \end{align*}\]

1.4.2. Some standard PGFs

We look at a few common probability distributions and derive their PGFs.

Example 1.8 (Binomial Distribution)

The binomial distribution is the distribution of the number of successes out of \(N\) trials if each trial has probability \(p\) of success independently of the others. We can think of this as the number of heads from \(N\) flips of a (possibly weighted) coin with probability \(p\) of heads.

Consider \(N\) trials, each with success probability \(p\). The probability of \(k\) successes is \(\binom{N}{k} p^k (1-p)^{N-k}\) (this is because there are \(\binom{N}{k}\) sequences that give \(k\) successes and \(N-k\) failures. Each of those sequences occurs with probability \(p^k (1-p)^{N-k}\)).

Then the PGF is

\[\begin{align*} \mu_N(x) &= \sum_{k=0}^N \binom{N}{k} (1-p)^{N-k}p^k x^k\\ &= (px+(1-p) )^N\\ &= (1-p + px)^N \end{align*}\]

Remark 1.4

Notice that the PGF for the number of heads in \(N\) flips \(\mu_N(x)\) is the PGF \(\mu_1(x)\) for a single flip raised to the \(N\)th power: \(\mu_N(x) = \mu_1(x)^N\). We will learn later why this happens.

Example 1.9 (Geometric Distribution)

The geometric distribution is the number of flips of a (possibly weighted) coin needed until the first heads. If the first flip is heads, we count that as \(1\) (some people use a different definition and count just the number of tails before the first head, which would start at \(0\)). The version we use is the version provided by python’s numpy package.

The probability of exactly \(k\) trials is \((1-p)^{k-1} p\). So the PGF is

\[\begin{align*} \mu(x) &= \sum_{k=1}^\infty (1-p)^{k-1} p x^k\\ &= px \sum_{k=1}^\infty ((1-p)x)^{k-1}\\ &= \frac{px}{1-(1-p)x} \end{align*}\]

If we use the other version of the Geometric Distribution, not counting the final event, then \(\mu_{\text{other definition}}(x) = p/(1-(1-p)x)\).

Example 1.10 (Poisson Distribution)

The Poisson distribution can be thought of as the limiting behavior of the Binomial Distribution in the case that \(N \to \infty\) while \(pN \to \lambda\). In this case, the probability of a given \(k\) is \(\lambda^k e^{-\lambda}/k!\). So

\[\begin{align*} \mu(x) &= \sum_{k=0}^\infty \frac{\lambda^k e^{-\lambda}}{k!} x^k\\ &= e^{-\lambda} \sum_{k=0}^\infty \frac{(\lambda x)^k}{k!}\\ &= e^{-\lambda} e^{\lambda x}\\ &= e^{\lambda(x-1)} \end{align*}\]

Example 1.11 (Negative Binomial Distribution)

The Negative Binomial Distribution can be described in a similar way to the Geometric Distribution. Assuming that the success probability is \(p\), the number of failures that occur before \(r\) successes has a Negative Binomial Distribution. Note that unlike the Geometric Distribution, here we are not counting successes. The reason for this inconsistency is because python’s numpy package uses this version.

The probablity of \(N\) failures before the \(r\)’th success can be calculated by finding the probability that the \(N+r\)th trial is a success, and the first \(N+r-1\) trials have \(N\) failures and \(r-1\) successes. This is

\[ p_N = p\binom{N+r-1}{N} p^{r-1}(1-p)^N \]

So

\[\begin{align*} \mu(x) &= \sum_{N=0}^\infty \binom{N+r-1}{N} p^{r}(1-p)^N x^N\\ &= p^r \sum_{N=0}^\infty \binom{N+r-1}{N} [(1-p)x]^N\\ &= p^r \sum_{N=0}^\infty \frac{(N+r-1)(N+r-2) \cdot (N+1)}{(r-1)(r-2)\cdots 1} [(1-p)x]^N\\ &= \frac{p^r}{(r-1)(r-2)\cdots 1} \sum_{N=0}^\infty (N+r-1)(N+r-2) \cdot (N+1) [(1-p)x]^N\\ &= \frac{p^r}{(r-1)(r-2)\cdots 1} \frac{1}{(1-p)^{r-1}}\frac{d^{r-1}}{dx^{r-1}} \sum_{N=0}^\infty [(1-p)x]^{N+r-1}\\ &= \frac{p^r}{(r-1)(r-2)\cdots 1} \frac{1}{(1-p)^{r-1}} \frac{d^{r-1}}{dx^{r-1}} (1-(1-p)x)^{-1}\\ &= \frac{p^r}{(r-1)(r-2)\cdots 1} \frac{1}{(1-p)^{r-1}} (-1)(-2)\cdots(-(r-1))(1-(1-p)x)^{-r} [-(1-p)]^{r-1}\\ &= p^r (1-(1-p)x)^{-r}\\ &= \left(\frac{p}{1-(1-p)x}\right)^r \end{align*}\]

We can extend the Negative Binomial to non-integer values of \(r\). The distribution loses the interpretation as a number of successes and failures. This provides a family of distributions with two parameters which is valuable in parameter fitting because it is mathematically tractible and can have a wide range of shapes.

With integer powers \(r\), we have

\[ p_N = \binom{N+r-1}{N} p^{r}(1-p)^N \]

while with non-integer \(r\), we get

\[ p_N = \frac{\Gamma(N+r)}{N!\Gamma(r)}p^r (1-p)^N \]

where \(\Gamma(x)\) is the Gamma Function which is the analytic extension of the Factorial function to non-integer numbers, with \(\Gamma(M+1)=M!\) for \(M=0,1,2,\ldots\). (you aren’t expected to know how to calculate this - most programming languages provide a function to calculate it).

We still find the same form of the PGF

\[\mu(x) = \left(\frac{p}{1-(1-p)x}\right)^r\]

As with the Geometric Distribution, there is another version of the Negative Binomial Distribution, in which we would count the \(r\) successes as well as the failures. In this case we would have \(\mu_{\text{other definition}}(x) = \left( px/(1-(1-p)x)\right)^r\).

Remark 1.5

Note that the PGF for a Negative Binomial Distribution is equal to the \(r\)-th power of \(1/x\) times the Geometric Distribution PGF.

1.4.3. Self-test

1. Consider the sequence (A, Ar, Ar^2, \ldots).

   (a) Write down the generating function of this sequence in expanded (series) form.

   Answer (a)

   The generating function is

   \[ f(x) = A + Arx + Ar^2x^2 + Ar^3x^3 + \cdots \]

   (b) Use the formula for the geometric series to find \(f(x)\).

   Answer (b)

   We have

   \[\begin{align*} f(x) &= A + Arx + Ar^2x^2 + Ar^3x^3 + \cdots\\ &= A(1 + rx + (rx)^2 + \cdots)\\ &= A \frac{1}{1-rx} \end{align*}\]

   (c) For what values of \(x\) does the series converge?

   Answer (c)

   As long as \(|rx|<1\) the series converges, so we need \(|x|<1/|r|\).

2. (this extends the results of the previous question) Consider the function \(g(x) = \frac{5-4x}{x^2-3x+2}\).

   1. Show that \(g(x)=\frac{1}{1-x} + \frac{3/2}{1-x/2}\) (one could use partial fractions to break \(g\) up into two terms like this and find the coefficients, but for this question, there’s no need to derive it. Just verify that you can combine the terms to get the original \(g(x)\)).

   2. Expand the two fractions above into power series using Question 1.

   3. Use this to write down the power series of \(g(x)\). Find a formula for the \(n\)-th coefficient of the generating function.

   4. Using \(g(x) = \frac{5-4x}{x^2-3x+2}\), find \(g(0)\) and \(g'(0)\) though standard differentiation methods. Verify that the generating function you found in the previous step is equal to \(g(0) + g'(0)x + \cdots\).

3. Derive the Poisson distribution PGF from the Binomial Distribution PGF by using the fact that the Poisson distribution is the limit of the Binomial distribution as \(N \to \infty\) with \(p = \lambda/N\). The identity \(\lim_{N \to \infty} (1+x/N)^N = e^x\) will probably be useful.

4. Consider the series \(f(x) = 1 + x + x^2 + \cdots\).

   1. Find a way to write the PGF \(\mu(x)\) of a standard 6-sided die as \(c_1 x^{a_1} f(x) + c_2 x^{a_2} f(x)\). In your calculations, always treat \(f(x)\) as the infinite series.

   2. Now we will replace \(f(x)\) by the fraction \(1/(1-x)\). For the values of \(c_1, c_2, a_1, a_2\) found previously use Algebra to verify (for \(x \neq 1\)) \(\frac{c_1 x^{a_1} + c_2 x^{a_2}}{1-x}= \mu(x)\). That is, confirm that \(c_1 x^{a_1} + c_2 x^{a_2} = (1-x) \mu(x)\).

5. Consider the generating function \(f(x) = x/ (1-x-x^2)\) of the Fibonacci sequence given in Example 1.4.

   1. Using a calculator/computer find \(f(0.1)\) to 15 digits and \(f(0.01)\) to 30 digits.

   2. Explain what you see.

   3. Can you say what \(f(0.001)\) is to 45 digits without any automated calculations?

6. Using the Binomial Expansion in Example 1.3:

   1. Write out the generating function form of \((1+x)^{-1/2}\), manipulating the coefficients of \(x^n\) to be in terms of \(\binom{2n}{n}\).

   2. Set \(x=-y\) and use this to find the generating function form of \((1-y)^{-1/2}\).

   3. Set \(x = -4z\) and find the generating function form of \((1-4z)^{-1/2}\).