第 11–13 章 · 生成函数：离散概率的万能钥匙

把数列 $\{a_n\}$ 装进幂级数 $A(s) = \sum a_ns^n$，问题就从"数列运算"变成"函数运算"——求和变相乘、递推变方程、卷积变乘法。生成函数是 Feller 卷一技术含量最高的章节，也是组合与概率的共同命脉。

概率生成函数

非负整数值随机变量的 PGF：

性质清单：$g(1)=1$；$P(X=k) = g^{(k)}(0)/k!$（系数即分布）；$E[X] = g'(1)$、$\mathrm{Var} = g''(1) + g'(1) - (g'(1))^2$。独立和 = PGF 相乘：$n$ 个独立伯努利之和（二项分布）的 PGF 是 $(q+ps)^n$——二项分布的形状直接可读。

复合与分支：PGF 的高光应用

• 随机个随机变量之和（复合分布）：$S = X_1 + \cdots + X_N$，$N$ 独立于诸 $X$：$g_S(s) = g_N(g_X(s))$——复合一下，保险公司赔款总数、分支过程的族群大小全在这里；
• 分支过程（Galton-Watson）：每代个体独立按同分布繁殖， extinction 概率的方程 $q = g(q)$：后代均值 $\mu \le 1$ 时必灭，$\mu > 1$ 时存活概率 $1-q$（$q$ 是 $g$ 的最小不动点）——人口学、链式反应、递归算法退化的共同模型。

递推关系的机械化

差分方程 $a_n = c_1a_{n-1} + c_2a_{n-2}$ 两侧乘 $s^n$ 求和：左 = $A(s)$，右 = $c_1 sA(s) + c_2 s^2 A(s) + \text{初值修正}$——解出 $A(s)$（有理函数）再部分分式展开读系数。Fibonacci 数、掷骰子首次和目标的概率、赌徒破产的时间分布，全部同一流水线。

老师的提醒

• PGF 的两大杀器分清：求分布用系数（$\left[s^k\right]g$），求矩用导数（$g'(1), g''(1)$）——目标不同动作不同。
• 复合公式 $g_N(g_X(s))$ 的方向（谁套谁）容易记反：外层是"个数"的 PGF。

自检

• 由 $g(s)$ 读出期望与方差的公式。
• 推导复合分布的 PGF。
• Galton-Watson 过程灭绝的判据与 $q$ 的求法。

更深一层：生成函数是"数列的拉普拉斯变换"

概率生成函数 $g(s) = E[s^X]$ 的深层身份是离散分布的变换域表示——与拉普拉斯变换对连续信号做的事完全同构：时域的卷积变成变换域的乘法、微分变成乘 $n$、初值变成系数。这个"变换域思维"的三步工作流：编码（分布 → 函数）、在变换域做便宜的操作（相乘 = 独立求和、复合 = 随机个随机变量之和）、解码（系数读分布、导数读矩）。学过信号与系统的读者会认出：Z 变换与 PGF 是同一个东西在概率语境的名字——ee-0 的第 10 章与本章互为镜像。

分支过程（Galton-Watson）的灭绝理论是 PGF 的皇冠应用：灭绝概率 $q$ 是 $g(s) = q$ 的最小非负根，且 $\mu = g'(1) \le 1 \iff q = 1$（必灭）、$\mu > 1 \iff q < 1$（有存活概率 $1 - q$）。推导的关键一步是自洽方程 $g_{n+1}(s) = g(g_n(s))$（每一代都是上一代的复合）——"复合"在生成函数语言里只是一个函数代入。

推导细读：递推关系的"机械化求解流水线"

生成函数解线性递推的标准流水线值得练熟：递推 $a_n = c_1a_{n-1} + c_2a_{n-2}$ 两侧乘 $s^n$ 对 $n \ge 2$ 求和：

解出 $A(s)$（初值自动入账），部分分式展开读系数。Fibonacci：$A(s) = \frac{s}{1 - s - s^2} = \frac{1}{\sqrt5}\left(\frac{1}{1 - \varphi s} - \frac{1}{1 - \psi s}\right)$，读出 $F_n = \frac{\varphi^n - \psi^n}{\sqrt5}$（Binet 公式）——递推的代数解法比猜特征根更有通用性（非线性递推、含卷积的递推它都能处理）。

在真实世界里：从生成函数到"现代离散概率"

PGF 的思想延伸到整个离散概率与现代算法分析：矩母函数/特征函数（连续分布的推广，卷二主角——中心极限定理的现代证明语言）；算法平均复杂度分析（快速排序比较次数的生成函数、随机树的高度分布——Analytic Combinatorics 学派用复分析读生成函数的奇点来"直接读出"渐近分布）；随机图（Erdős–Rényi 相变的生成函数刻画）。Feller 卷一的最后三章是这一切的入口：学会把"计数问题"翻译成"函数运算"，离散数学就获得了连续数学的全部武器库。

专题深入：生成函数是"数列的拉普拉斯变换"完整版

概率生成函数 $g(s) = E[s^X]$ 的深层身份是离散分布的变换域表示——与拉普拉斯变换对连续信号做的事完全同构：时域的卷积变成变换域的乘法、微分变成乘 $n$、初值变成系数。这个"变换域思维"的三步工作流：编码（分布 → 函数）、在变换域做便宜的操作（相乘 = 独立求和、复合 = 随机个随机变量之和）、解码（系数读分布、导数读矩）。学过信号与系统的读者会认出：Z 变换与 PGF 是同一个东西在概率语境的名字——ee-0 的第 10 章与本章互为镜像。

分支过程（Galton-Watson）的灭绝理论是 PGF 的皇冠应用：灭绝概率 $q$ 是 $g(s) = q$ 的最小非负根，且 $\mu = g'(1) \le 1 \iff q = 1$（必灭）、$\mu > 1 \iff q < 1$（有存活概率 $1 - q$）。推导的关键一步是自洽方程 $g_{n+1}(s) = g(g_n(s))$（每一代都是上一代的复合）——"复合"在生成函数语言里只是一个函数代入。

数学细节展开：递推关系的"机械化求解流水线"完整版

生成函数解线性递推的标准流水线值得练熟：递推 $a_n = c_1a_{n-1} + c_2a_{n-2}$ 两侧乘 $s^n$ 对 $n \ge 2$ 求和：

解出 $A(s)$（初值自动入账），部分分式展开读系数。Fibonacci：$A(s) = \frac{s}{1 - s - s^2} = \frac{1}{\sqrt5}\left(\frac{1}{1 - \varphi s} - \frac{1}{1 - \psi s}\right)$，读出 $F_n = \frac{\varphi^n - \psi^n}{\sqrt5}$（Binet 公式）——递推的代数解法比猜特征根更有通用性（非线性递推、含卷积的递推它都能处理）。

工程案例细节：从生成函数到"现代离散概率"（工程版）

PGF 的思想延伸到整个离散概率与现代算法分析：矩母函数/特征函数（连续分布的推广，卷二主角——中心极限定理的现代证明语言）；算法平均复杂度分析（快速排序比较次数的生成函数、随机树的高度分布——Analytic Combinatorics 学派用复分析读生成函数的奇点来"直接读出"渐近分布）；随机图（Erdős–Rényi 相变的生成函数刻画）。Feller 卷一的最后三章是这一切的入口：学会把"计数问题"翻译成"函数运算"，离散数学就获得了连续数学的全部武器库。