1.7. Linear Combinations of Generating Functions

Linear combinations of generating functions behave largely as expected.

Consider \(f(x) = f_0 + f_1 x + f_2 x^2 + \cdots\) and \(g(x) = g_0 + g_1 x + g_2 x^2 + \cdots\). Then the linear combination \(\alpha f(x) + \beta g(x)\) is

\[ \alpha f(x) + \beta g(x)= \sum_{n=0}^\infty (\alpha f_n + \beta g_n) x^n \]

which is the generating function for the corresponding linear combination of the sequences. This generalizes to linear combinations of more than two functions.

1.7.1. Convex Combination of PGFs

When working with PGFs, we are typically interested in Convex Combinations:

Definition 1.3 (Convex Combination)

A Convex Combination is a special case of a linear combination in which all coefficients are non-negative and sum to \(1\) — that is, they can be thought of as a collection of probabilities.

Consider two PGFs \(\mu_1(x) = p_0 + p_1 x + p_2 x^2 + \cdots\) and \(\mu_2(x) = q_0 + q_1 x + q_2 x^2 + \cdots\) and the corresponding probability distributions.

Let \(\pi_1\) and \(\pi_2\) be probabilities, \(\pi_1 + \pi_2 = 1\). Then the convex combination

\[ \psi(x) = \pi_1 \mu_1(x) + \pi_2 \mu_2(x) = \sum_{n=0}^\infty (\pi_1 p_n + \pi_2 q_n)x^n \]

is also a PGF. It corresponds to the following method for using the distributions corresponding to \(\mu_1\) and \(\mu_1\) to choose an integer \(k\):

• We first decide with probability \(\pi_1\) to use \(\mu_1(x)\) and with probability \(\pi_2\) to use \(\mu_2(x)\).

• Then we choose an integer \(k\) using the distribution corresponding to either \(\mu_1(x)\) or \(\mu_2(x)\).

(you may have seen this called a mixture distribution - where there are multiple distributions and the first step in choosing a random number is to randomly choose which distribution to use)

Example 1.20

Consider a fair coin, for which tails is considered \(0\) and heads \(1\), and a standard \(6\)-sided die. The corresponding PGFs are

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

Let us assume that with probability \(\pi_1=1/4\) we decide to flip the coin while with probability \(\pi_2=3/4\) we roll the die. Then the PGF for the result is

\[\begin{align*} \psi(x) &= \frac{1}{4} \mu_1(x) + \frac{3}{4} \mu_2(x) \\ &= \frac{1+x}{8} + \frac{x+x^2+x^3+x^4+x^5+x^6}{8}\\ &= \frac{1+2x+x^2+x^3+x^4+x^5+x^6}{8} \end{align*}\]

Notice the coefficient of \(x\) is different from the others.

We can check this by enumerating the possibilities:

• The probability that we decide to flip the coin and that we then get \(0\) or \(1\) is \(1/8\) for each. We get \(1/8\) by combining the probability \(1/4\) that we flip the coin with the probability \(1/2\) that we get \(0\) or \(1\) conditional on flipping the coin.

• The probability that we decide to roll the die and then get one of \(1, 2, \ldots, 6\) is \(1/8\) for each. This is \(3/4\) that we decide to roll the die and then \(1/6\) for \(1, 2, \ldots, 6\) conditional on rolling the die.

• So every numerical value has probability \(1/8\), except for \(1\), which can occur two different ways with combined probability \(2/8\).

We can generalize this to multiple distributions:

Theorem 1.1 (Linear combination of PGFs)

Assume that we have a (possibly infinite) set of PGFs \(\mu_1(x), \mu_2(x), \ldots\). We choose a number \(n\) by first choosing the distribution corresponding to \(\mu_i(x)\) with probability \(\pi_i\), and then we choose \(n\) from the distribution. The resulting distribution for \(n\) has PGF

\[ \psi(x) = \sum_{i=1}^\infty \pi_i\mu_i(x) \]

Proof. To prove this we must show that the PGF for this process is the given convex combination of the original PGFs. We will construct the PGF for this process by finding \(p_n\), the probability of \(n\).

Assume \([x^n]\mu_i(x) = p_{i,n}\), that is, \(\mu_i(x) = \sum_n p_{i,n} x^n\). The probability of choosing distribution \(i\) and then choosing \(n\) is \(\pi_i p_{i,n}\). So the probability of choosing \(n\) is

\[ p_n = \sum_i \pi_i p_{i,n} \]

So setting \(\xi(x) = \sum_n p_n x^n\) to be the PGF for \(n\), we find

\[\begin{align*} \xi(x) &= \sum_n p_n x^n\\ &= \sum_n \sum_i \pi_i p_{i,n} x^n\\ &= \sum_i \pi_i \sum_n p_{i,n} x^n\\ &= \sum_i \pi_i \mu_i(x) \end{align*}\]

1.7.2. Self-test

1. In a board game, players can choose to roll one die or two dice, and then whenever any player rolls a sum \(k\), each player receives a benefit based on cards in their hand. Assuming a player’s probability of choosing to roll one die is \(q\), find the PGF for the outcome of the roll.