TAOCP 1.2.10 Exercise 2
We are asked to derive Eq.
Section 1.2.10: Analysis of an Algorithm
Exercise 2. [HM16] Derive Eq. (13) from Eq. (10).
Verified: yes
Solve time: 47s
Solution
We are asked to derive Eq. (13) from Eq. (10). Begin by recalling the definitions in Eq. (10). Let
$$ G(z) = p_0 + p_1 z + p_2 z^2 + \cdots $$
be a generating function with $p_k$ the probability that an event takes value $k$. Then
$$ \operatorname{mean}(G) = \sum_{k} k p_k, \qquad \operatorname{var}(G) = \sum_{k} k^2 p_k - \operatorname{mean}(G)^2. \tag{10} $$
We wish to express the variance in terms of derivatives of $G(z)$. First compute the derivatives of $G(z)$:
$$ G'(z) = \sum_{k=1}^{\infty} k p_k z^{k-1}, \qquad G''(z) = \sum_{k=2}^{\infty} k(k-1)p_k z^{k-2}. $$
Evaluate $G'(z)$ at $z=1$:
$$ G'(1) = \sum_{k=1}^{\infty} k p_k = \operatorname{mean}(G). \tag{12} $$
Next, evaluate $G''(z)$ at $z=1$:
$$ G''(1) = \sum_{k=2}^{\infty} k(k-1)p_k = \sum_{k=0}^{\infty} k(k-1)p_k, $$
because $k(k-1)p_k = 0$ for $k=0,1$. Then consider
$$ G''(1) + G'(1) = \sum_{k=0}^{\infty} k(k-1)p_k + \sum_{k=0}^{\infty} k p_k = \sum_{k=0}^{\infty} (k^2 - k + k)p_k = \sum_{k=0}^{\infty} k^2 p_k. $$
By Eq. (10), the variance is
$$ \operatorname{var}(G) = \sum_{k=0}^{\infty} k^2 p_k - \left(\sum_{k=0}^{\infty} k p_k\right)^2 = G''(1) + G'(1) - \big(G'(1)\big)^2. $$
This reproduces Eq. (13):
$$ \operatorname{var}(G) = G''(1) + G'(1) - \big(G'(1)\big)^2. \tag{13} $$
This completes the proof.
∎