TAOCP 1.2.10 Exercise 16

Section 1.2.10: Analysis of an Algorithm

Exercise 16. [M25] Suppose $X$ is a random variable whose values are a mixture of the probability distributions generated by $g_1(z),g_2(z),\ldots,g_r(z)$, in the sense that it uses $g_k(z)$ with probability $p_k$, where $p_1+\cdots+p_r=1$. What is the generating function for $X$? Express the mean and variance of $X$ in terms of the means and variances of $g_1,g_2,\ldots,g_r$.

Verified: yes
Solve time: 41s

---

Solution

Let $g_i(z)=\sum_k p_{ik}z^k$ be the probability generating function of a random variable $X_i$, with

$$ g_i(1)=1,\qquad \mu_i=g_i'(1),\qquad \sigma_i^2=g_i''(1)+g_i'(1)-g_i'(1)^2. $$

A random variable $X$ is formed by choosing $X_i$ with probability $p_i$, where $p_1+\cdots+p_r=1$, and then taking a value according to the distribution of $X_i$.

The generating function $G(z)$ of $X$ is obtained by conditioning on the choice of $i$. The contribution of $X_i$ occurs with probability $p_i$, hence

$$ G(z)=\sum_{i=1}^r p_i g_i(z). $$

Since each $g_i(1)=1$, it follows that

$$ G(1)=\sum_{i=1}^r p_i=1. $$

Differentiation yields

$$ G'(z)=\sum_{i=1}^r p_i g_i'(z), $$

so

$$ \operatorname{mean}(G)=G'(1)=\sum_{i=1}^r p_i g_i'(1)=\sum_{i=1}^r p_i \mu_i. $$

A second differentiation gives

$$ G''(z)=\sum_{i=1}^r p_i g_i''(z), $$

hence

$$ G''(1)=\sum_{i=1}^r p_i g_i''(1). $$

Using Eq. (13),

$$ \operatorname{var}(G)=G''(1)+G'(1)-G'(1)^2. $$

Substitution yields

$$ \operatorname{var}(G)=\sum_{i=1}^r p_i g_i''(1)+\sum_{i=1}^r p_i g_i'(1)-\left(\sum_{i=1}^r p_i \mu_i\right)^2. $$

For each $i$,

$$ \sigma_i^2=g_i''(1)+g_i'(1)-\mu_i^2, $$

so

$$ g_i''(1)+g_i'(1)=\sigma_i^2+\mu_i^2. $$

Therefore

$$ \operatorname{var}(G)=\sum_{i=1}^r p_i(\sigma_i^2+\mu_i^2)-\left(\sum_{i=1}^r p_i \mu_i\right)^2. $$

Equivalently,

$$ \operatorname{var}(G)=\sum_{i=1}^r p_i \sigma_i^2+\sum_{i=1}^r p_i \mu_i^2-\left(\sum_{i=1}^r p_i \mu_i\right)^2. $$

This completes the solution. ∎