1.6. Differentiation of Generating Functions

A common operation that we will do with generating functions is to take their derivative. If we have a generating function

\[ f(x) = c_0 + c_1 x + c_2 x^2 + \cdots = \sum_{n=0}^\infty c_n x^n \]

then

\[ f'(x) = c_1 + 2 c_2 x + 3 c_2 x^2 + \cdots = \sum_{n=0}^\infty n c_n x^{n-1} \]

However, normally we want to write this so that we use \(x^n\), not \(x^{n-1}\). Then

\[ f'(x) = \sum_{n=0}^\infty (n+1) c_{n+1} x^n \]

So differentiating corresponds to multiplying the coefficient of \(x^n\) by \(n\) and reducing the power of \(x\) by \(1\). In terms of the corresponding sequence of numbers, we multiply the \(n\)th number by \(n\) and shift the indices so that it becomes the \(n-1\)st number.

Example 1.15 (Differentiation of a Poisson distribution PGF)

Consider the PGF of a Poisson distribution with mean \(2\):

\[ \mu(x) = \sum_{n=0}^\infty \frac{2^n e^{-2}}{n!} x^n \]

If we differentiate this with respect to \(x\) we get

\[\begin{align*} \mu'(x) &= \frac{d}{dx} \sum_{n=0}^\infty \frac{2^n e^{-2}}{n!} x^{n}\\ &= \sum_{n=0}^\infty n \frac{2^n e^{-2}}{n!} x^{n-1}\\ &= \sum_{n=0}^\infty (n+1) \frac{2^{n+1}e^{-2}}{(n+1)!} x^n \end{align*}\]

where the final line reindexes the sum, eliminating the initial \(0\) term. This is illustrated in Fig. 1.3.

Fig. 1.3 The “clothesline” (i.e., series) representation of the PGF of the Poisson distribution with mean \(2\) and its derivative.

If we don’t want to shift the indices, that is, we want to keep the same power of \(x\) we need to undo the reduction in power of \(x\). To do this, we multiply by \(x\).

\[ x f'(x) = 0c_0 + 1 c_1 x + 2 c_2 x^2 + \cdots= \sum_{n=0}^\infty n c_n x^n \]

Example 1.16 (Differentiation of a Poisson distribution PGF)

If we start with the derivative of the PGF of a Poisson distribution with mean \(2\):

\[ \mu'(x) = \sum_{n=0}^\infty (n+1)\frac{2^{n+1} e^{-2}}{(n+1)!} x^n \]

and multiply by \(x\) we get

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

where the final line reindexes the sum, eliminating the initial \(0\) term. This is shown in Fig. 1.4. The result is

Fig. 1.4 The “clothesline” (i.e., series) representation showing the multiplication of \(\mu'(x)\) by \(x\).

So differentiating a generating function and then multiplying it by \(x\) is equivalent to multiplying each \(n\)th term of the sequence by \(n\). Although we can do this with a series expansion, the benefit of this typically comes from when we have a closed form version of the function.

We will do this often. For notational compactness we will use \(x \partial_x\) to denote taking the \(x\) derivative and then multiplying the result by \(x\):

\[ x \partial_x f(x) = x f'(x) = \sum n c_n x^n \]

Example 1.17 (\(x \partial_x\) of the Poisson Distribution PGF)

Consider the PGF of the Poisson Distribution of mean 2:

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

When we take \(x \partial_x \mu(x)\), we get

\[\begin{align*} x \partial_x \mu_x &= x \frac{d}{dx} e^{2(x-1)}\\ &= x (2e^{2(x-1)})\\ &= 2x e^{2x-1} \end{align*}\]

This is illustrated in figure Fig. 1.5.

Fig. 1.5 Illustration of \(x \partial_x\) for the PGF of the Poisson distribution of mean \(2\), using the “bag” representation.

When we perform the operation repeatedly, we will use the notation \((x \partial_x)^k\):

\[ (x \partial_x)^k f(x) = x \partial_x (x \partial_x)^{k-1} f(x) = \sum n^k c_n x^n \]

Example 1.18 (The sequence \(0^k, 1^k, 2^k, \ldots\))

Consider the generating function

\[ A_k(x)= \sum_{n=0}^\infty n^k x^n = 0^k + 1^k x + 2^k x^2 + 3^k x^3 + \cdots \]

where \(0^0\) is understood to be \(1\).

We have previously seen that

\[ A_0(x) = \sum_{n=0}^\infty 1 x^n = \frac{1}{1-x} \]

To find \(A_1(x) = \sum_{n=0}^\infty n x^n\) which corresponds to multiplying the \(n\)th term of the series in \(A_0(x)\) by \(n\), we simply differentiate \(A_0(x)\) and multiply by \(x\):

\[\begin{align*} A_1(x) &= \sum_{n=0}^\infty nx^n\\ &= x \partial_x A_0(x)\\ &= x \partial_x (1-x)^{-1}\\ &= x(1-x)^{-2} \end{align*}\]

To find each successive \(A_k(x)\) we repeat this with \(A_k(x) = x \partial_x A_{k-1}(x) = (x \partial_x)^k \frac{1}{1-x}\).

Example 1.19 (Calculating a Combinatorial Identity)

Consider the question: What is the sum \(\sum_{n=0}^N n^2 \binom{N}{n}\)?

To find this sum, we will actually recast this as a special case of the more general question: What is the sum \(\sum_{n=0}^N n^2 \binom{N}{n}x^n\)?

When \(x=1\), this reduces to the original equation.

We observe that

\[\begin{align*} \sum_{n=0}^N n^2 \binom{N}{n} x^n &= (x \partial_x)^2 \sum_{n=0}^N \binom{N}{n} x^n\\ &= (x \partial_x)^2 (1+x)^N\\ &= x \partial_x \left(x N(1+x)^{N-1}\right)\\ &= x \left( N(1+x)^{N-1} + N(N-1)(1+x)^{N-2}\right)\\ &= Nx(1+x)^{N-1} + N(N-1) x(1+x)^{N-2} \end{align*}\]

The original question corresponded to \(x=1\), so we substitute \(x=1\) and get

\[\sum_{n=0}^N n^2 \binom{N}{n} = 2^{N-1} N + 2^{N-2}N(N-1)\]

1.6.1. Probability Generating Function applications

In probability generating functions, the derivative has an important role to play.

1.6.1.1. Moments of a distribution

For a given distribution of the integers, we are often interested in the moments of the distribution, defined so that the \(r\)th moment is

\[\langle D^r \rangle = \mathbb{E}[D^r] = \sum_{n=0}^\infty n^r p_n \]

If we take \(\mu(x) = \sum p_n x^n\) to be the PGF of this distribution, then

\[\begin{align*} \langle D \rangle &= \mathbb{E}[D^1] =\sum_{n=0}^\infty n p_n= \sum_{n=0}^\infty n p_n 1^n\\ & = \left[ x \partial_x \mu(x) \right|_{x=1}\\ \langle D^2 \rangle &= \mathbb{E}[D^2] = \sum_{n=0}^\infty n^2 p_n= \sum_{n=0}^\infty n^2 p_n 1^n \\ &= \left[ (x \partial_x)^2 \mu(x) \right|_{x=1} \end{align*}\]

and in general:

\[\begin{align*} \langle D^r \rangle &= \mathbb{E}[D^r] =\sum_{n=0}^\infty n^r p_n= \sum_{n=0}^\infty n^r p_n 1^n \\ &= \left[ (x \partial_x)^r \mu(x)\right|_{x=1} \end{align*}\]

Notice that \(\langle D^0 \rangle = \sum_{n=0}^\infty p_n 1^n = 1\). So \(\mu(1)=1\) if \(\mu(x)\) is a PGF.

1.6.1.2. Factorial Moments

Sometimes we are interested in the factorial moments:

\[ \langle (D)_r\rangle = \mathbb{E}[D(D-1)\cdots(D-r+1) ] = \sum_{n=0}^\infty n(n-1)\cdots (n-r+1) p_n \]

In this case

\[\begin{align*} \langle (D)_1 \rangle &= \mathbb{E}[D] =\sum_{n=0}^\infty n p_n= \sum_{n=0}^\infty n p_n 1^{n-1} \\ & = \mu'(1)\\ \langle (D)_2 \rangle &= \mathbb{E}[D(D-1)] = \sum_{n=0}^\infty n(n-1) p_n= \sum_{n=0}^\infty n(n-1) p_n 1^{n-2} \\ &= \mu''(1) \end{align*}\]

and in general:

\[\begin{align*} \langle (D)_r \rangle &= \mathbb{E}[D(D-1) \cdot (D-r+1)] =\sum_{n=0}^\infty n(n-1)\cdots (n-r+1) p_n= \sum_{n=0}^\infty n(n-1)\cdots(n-r+1) p_n 1^{n-r} \\ &= \mu^{(r)}(1) \end{align*}\]

1.6.2. Self-test

1. Using the PGFs of the Binomial, Geometric, and Poisson distributions, find the average of each distribution in terms of the parameters appearing in the PGFs.

2. Find the sum \(\sum_{n=0}^N n \binom{N}{n}\).

3. Find the sum \(\sum_{j=0}^\infty j r^j\) for \(|r|<1\).

4. Consider a weighted coin that comes up heads with probability \(p\) and tails with probability \(1-p\). Use differentiation of PGFs to find out how many flips on average it takes until the first heads (counting the final heads as a flip).

   1. Explain why the probability of \(n\) flips is \(p(1-p)^{n-1}\), so the average is \(p\sum n (1-p)^{n-1}\).

   2. Write this in terms of \(\mu'(1-p)\) for some PGF \(\mu(x)\) and find \(\mu(x)\).

   3. Calculate the sum.