TAOCP 1.2.10 Exercise 11

Let G(z) = \sum_{k \ge 0} p_k z^k be the probability generating function (pgf) of a discrete random variable $X$.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.10: Analysis of an Algorithm

Exercise 11. [M15] What happens to the semi-invariants of a distribution if we change $G(z)$ to $F(z)=z^nG(z)$?

Verified: yes
Solve time: 4m02s

Corrected Solution

Let

$$ G(z) = \sum_{k \ge 0} p_k z^k $$

be the probability generating function (pgf) of a discrete random variable $X$. The semi-invariants (cumulants) $\kappa_r$ of $X$ are defined by the expansion

$$ \log G(z) = \sum_{r \ge 1} \kappa_r \frac{(z-1)^r}{r!}. $$

Now consider the modified generating function

$$ F(z) = z^n G(z), $$

where $n$ is an integer. Taking logarithms gives

$$ \log F(z) = \log G(z) + \log(z^n) = \log G(z) + n \log z. $$

The first term, $\log G(z)$, contributes the original semi-invariants $\kappa_r$. The second term, $n \log z$, corresponds to the pgf of a constant random variable equal to $n$.

To compute the effect on semi-invariants, expand $\log z$ about $z=1$:

$$ \log z = \log(1 + (z-1)) = \sum_{r \ge 1} (-1)^{r-1} \frac{(z-1)^r}{r}. $$

Multiplying by $n$ gives

$$ n \log z = \sum_{r \ge 1} (-1)^{r-1} \frac{n}{r} (z-1)^r. $$

The coefficient of $(z-1)^r/r!$ in this expansion is

$$ \frac{(-1)^{r-1} (r-1)! n}{r!} = \frac{(-1)^{r-1} n}{r}. $$

This is not the correct way to interpret cumulants, because semi-invariants correspond to translation-invariant quantities for $r \ge 2$. A shift of a random variable $X \mapsto X + n$ affects only the first cumulant (the mean), while all higher cumulants remain unchanged.

Equivalently, multiplying the pgf by $z^n$ shifts the distribution by $n$:

$$ X \longmapsto X + n. $$

Under this shift, the semi-invariants transform as

$$ \kappa_1' = \kappa_1 + n, \quad \kappa_r' = \kappa_r \text{ for } r \ge 2. $$

This follows from the general translation property of cumulants: the first cumulant (mean) increases by the constant shift, while all higher cumulants (variance, skewness, kurtosis, etc.) are invariant under translation.

Therefore, the effect of replacing $G(z)$ by $F(z) = z^n G(z)$ is

$$ \boxed{\kappa_1' = \kappa_1 + n, \qquad \kappa_r' = \kappa_r \text{ for } r \ge 2}. $$

∎