Composition of PGFs

Contents

1.9. Composition of PGFs#

In this section, we focus just on PGFs and do not consider Ordinary Generating Functions. Given two PGFs, we would like to know how to interpret \(\mu_1(\mu_2(x))\).

We have learned the following facts for PGFs:

  • Theorem 1.1: If we take a linear combination of PGFs \(\mu_1(x)\), \(\mu_2(x)\), \(\ldots\) where the coefficients themselves are probabilities summing to \(1\):

    \[\psi(x) = \sum \pi_i \mu_i(x)\]

    then \(\psi(x)\) is a PGF and the corresponding distribution can be thought of as choosing the distribution for \(\mu_i\) with probability \(\pi_i\) and then choosing \(n\) from that distribution.

  • Corollary 1.2: Given the PGF \(\mu(x)\), the result of multiplying it by itself \(k\) times gives:

    \[\psi_k(x) = \mu(x)^k\]

    then \(\psi_k(x)\) is a PGF and the corresponding distribution can be thought of as adding \(k\) numbers chosen independently from the distribution for \(\mu(x)\).

Now we consider two arbitrary PGFs

\[\begin{align*} \mu_1(x) &= \sum_{k=0}^\infty p_k x^k\\ \mu_2(x) &= \sum_{m=0}^\infty q_m x^m \end{align*}\]

We want to know how we can interpret

\[ \psi(x) = \mu_1(\mu_2(x)) \]

Let’s introduce a definition and then look at an example before we do the general case.

Definition 1.4 (Randomly stopped sum)

A sum \(\sum_{j=1}^K M_j\) where \(K\) is a random non-negative integer from a distribution and \(M_j\) are all random non-negative integers from another distribution is a randomly stopped sum

Example 1.23 (Cash machine PGF)

Let \(\mu_1(x) = \sum_{k=0}^\infty p_k x^k\) be the PGF for the number of customers who come to a cash machine during a day and \(\mu_2(x)= \sum_{m=0}^\infty q_m x^m\) be the PGF for the amount of money a random customer withdraws. What would be the PGF for the total amount of money withdrawn from the cash machine during a day?

This is an example of a randomly-stopped sum. The number of individuals who will withdraw money corresponds to the random number \(K\) and the amount that each withdraws corresponds to the random number \(M_j\) in Definition 1.4.

Let’s first think through separate cases based on \(k\), how many customers arrive. We’ll find the PGF assuming that \(k\) is known. Then we’ll combine the PGFs for each possible \(k\) into a complete PGF. Conditional on knowing \(k\), the PGF of the amount withdrawn is \(\xi_k(x)=[\mu_2(x)]^k\) by Corollary 1.2.

The PGF for the total amount withdrawn is \(\psi(x) = \sum_{k=0}^\infty p_k \xi_k(x)\) by Theorem 1.1. Substituting \([\mu_2(x)]^k\) for \(\xi_k(x)\) we get

\[ \psi(x) = \sum_{k=0}^\infty p_k [\mu_2(x)]^k = \mu_1(\mu_2(x)) \]

is the PGF for the total amount withdrawn.

Returning to the general case of \(\psi(x) = \mu_1(\mu_2(x))\), we have

\[ \psi(x) = \sum_{k=0}^\infty p_k [\mu_2(x)]^k \]

The \(k\)-th power of \(\mu_2(x)\) is the PGF for sum of \(k\) numbers drawn from the distribution of \(\mu_2(x)\). The linear combination of these corresponds to using the distribution for \(\mu_1(x)\) to choose the random number of terms to include in the sum.

This leads to

Theorem 1.5 (Composition of PGFs and randomly-stopped sums)

Given PGFs \(\mu_1(x)\) and \(\mu_2(x)\), the composition \(\psi(x) = \mu_1(\mu_2(x))\) is the PGF \(\sum_n p_nx^n\) for the randomly stopped sum:

\[ \sum_{j=1}^K M_j \]

where we

  • the random value \(K\) is chosen from the distribution of \(\mu_1(x)\) and

  • each random value \(M_j\) is chosen from the distribution of \(\mu_2(x)\).

Definition 1.5 (Function Composition)

The composition of two functions \(\mu_1(x)\) and \(\mu_2(x)\) is the new function \(\mu_1(\mu_2(x))\).

Remark 1.7 (Function Composition Notation)

Sometimes the notation \(\psi(x) = \mu_1 \circ \mu_2(x)\) of \((\mu_1\circ \mu_2)(x)\) is used to denote function composition, but we will stick to \(\mu_1(\mu_2(x))\) in these notes.

Our theorem states that the PGF of a randomly stopped sum can be found by using composition \(\psi(x)=\mu_1(\mu_2(x))\) where \(\mu_1(x)\) is the PGF corresponding to \(K\) and \(\mu_2(x)\) is the PGF corresponding to the \(M_j\).

We illustrate this in the following example in which \(\mu_1(x)=\mu_2(x)\):

Example 1.24

Consider one person who rolls a single standard six-sided die with PGF \(\mu(x) = (x+x^2+ \cdots + x^6)/6\). Let \(k\) be the resulting random number.

Then \(k\) individuals are chosen from the population, each of whom rolls a six-sided die. Add their results together to get \(n\). The PGF for \(n\) is \(\psi(x)=\mu(\mu(x))\).

This is illustrated in figure Fig. 1.9.

../../_images/InfectiousDice.png

Fig. 1.9 If we roll one die to choose the random number \(k\) and then sum the rolls of \(k\) dice to get \(n\), then the PGF of the final sum is \(\mu(\mu(x))\), illustrating Example 1.24.#

1.9.1. Self-test#

instructor’s note to self: I’ve added problems, starting from Q3, to this since the start of the subject. I don’t want to change the ordering during the course. After the course, re-order the questions.

  1. Consider the dice rolling in Example 1.24. Set \(X_0=1\). For \(g=1, 2, 3\), find \(X_g\) by having \(X_{g-1}\) individuals each roll a die and setting \(X_g\) to be the sum.

    1. Show that the PGF of \(X_1\) is \(\psi(x)\) where \(\psi(x)\) is the PGF of a single die.

    2. Explain why the PGF of \(X_2\) is \(\psi(\psi(x))\). [hint: Example 1.24 should be helpful for this.]

    3. What is the PGF of \(X_3\)?

  2. Consider a single infected individual introduced to a very large population. Assume that the number of new infections caused by one infectious individual has PGF \(\mu(x)\). Explain why the number of individuals reached in two transmission steps has PGF \(\mu(\mu(x))\).

  3. Consider the process where a fair coin with numbers \(1\) and \(2\) is flipped. Based on the result, roll a standard die. What is the PGF of the outcome? What if the coin is biased so that \(p_1=p\)?

  4. Flip a fair coin with numbers \(1\) and \(2\) on its sides. Let \(k\) be the result. Then roll \(k\) standard dice and sum the result to get \(m\). Then flip \(m\) coins and sum the result to get \(n\).

    1. What is the PGF \(\mu_{\text{coin}}(x)\) of the coin?

    2. What is the PGF \(\mu_{\text{die}}(x)\) of a single die?

    3. What is the PGF of \(n\) in terms of \(\mu_{\text{coin}}(x)\) and \(\mu_{\text{die}}(x)\)?

    4. Your answer above probably has \(\mu_{\text{coin}}\) appear twice. Which appearance corresponds to the first flip?

  5. Recall that the derivative of a PGF, evaluated at \(x=1\) gives the expected value. Use this property to show that a randomly stopped sum has expected value equal to the expected number of terms times the expected value of each term.

  6. Insurance claims, such as for fires or floods do not arrive as independent events. If one house is affected by a flood or a bushfire, it is likely that others are as well. Assume that the number of claims per month has some distribution whose PGF is \(\mu(x)\). Assume also that the size of claims are independent of one another and have a PGF \(\xi(x)\).

    1. How can we use PGFs to calculate the mean amount of claims during a month?

    2. The variance of a function is \(\mathbb{E}[X^2] - \mathbb{E}[X]^2\). How can we use PGFs to calculate the variance of the monthly claims?

Contents