「Note」Probability Generating Function

It’s time to roll the dice.

$\mathtt{Definition}$

令 $X$ 为取值非负的随机变量，那么 $X$ 的概率生成函数 $\mathtt{Probability\ Generating\ Function}$ 为
$$ \begin{aligned} G_x(z) = \sum_{k \ge 0} \mathrm{Pr}(X = k) z^k \end{aligned} $$
根据上式可以得知该生成函数各项系数均非负，且其和为 $1$ ，即是
$$ \begin{aligned} G_x(1) = 1 \end{aligned} $$
那么反过来，任何非负系数且满足 $G_x(1) = 1$ 的幂级数 $G_x$ 均为某随机变量的生成函数。

$\mathtt{Average \ \& \ Variance}$

$\mathtt{Average}$

$$ \begin{aligned} \mathrm{E}(X) &= \sum_{k \ge 0} k \mathrm{Pr}(X = k) \\ &= \sum_{k \ge 0} \mathrm{Pr}(X = k) k \cdot 1^{k - 1} \\ &= G_{x}^{'} (1) \end{aligned} $$

进而有
$$ \begin{aligned} \mathrm{E}(X^{\underline{k} }) = G_x^{k}(1) (k \not = 0) \end{aligned} $$

$\mathtt{Variance}$

$$ \begin{aligned} \operatorname{D}(X)&=\operatorname{E}(X^2)-\operatorname{E}(X)^2\\ &=G_{X}^{''}(1)+G_{X}^{'}(1)-G_{X}^{'}(1)^2 \end{aligned} $$

即是说在知道 $G_{X}^{''}(1)$ 和 $G_x^{'}(1)$ 的情况下就可以得到 $\mathrm{D}(X)$ 。

$\mathtt{Multiplication}$

若两个随机变量 $X, Y$ 互相独立，那么有
$$ \begin{aligned} \operatorname{Pr}(X+Y=n)=&\sum_{k}\operatorname{Pr}(X=k \wedge Y=n-k)\\ =&\sum_{k}\operatorname{Pr}(X=k)\operatorname{Pr}(Y=n-k)\\ \end{aligned} $$
写成卷积的形式
$$ \begin{aligned} G_{X+Y}(z)=G_{X}(z)G_{Y}(z) \end{aligned} $$