浅谈 PGF 概率生成函数

· · 算法·理论

本文同步发表于 cnblogs.

前言：笔者是区在做P4548 [CTSC2006] 歌唱王国时发现自己是区这个东西非常牛逼，跑来学习一下，第一次写学习笔记，错误地方恳请各位 dsa 指出。

设 X 为取值于 \mathbb{N} 的随机变量，其概率分布为 p_k=\mathbb{P}(X=k)，则定义 X 的概率生成函数（PGF）为 G_X(s)=\mathbb{E}[s^X]=\sum\limits_{k\ge 0} p_ks^k，其中 s\in[-1,1] 同时约定 0^0=1.

由于 \sum\limits_{k\ge 0}p_k=1，该幂级数在 [-1,1] 上绝对收敛，因此 G_X 在 (-1,1) 内无穷次可导，且在收敛区间内可逐项求导，显然有基础事实 G_X(0)=p_0,G_X(1)=\sum\limits_{k\ge 0} p_k=1.

据此定义条件 PGF，即在给定事件或给定另一个随机变量条件下的 PGF，如给定事件 A 则 G_{X|A}(s)=\mathbb{E}[s^X|A]，给定事件 Y=y 则 G_{X|Y}(s|y)=\mathbb{E}[sX|Y=y]，同理有 G_{X|A}(1)=G_{X|Y}(1|y)=1，且条件矩可以由求导得到，即 \mathbb{E}[X|A]=G'_{X|A}(1),\mathbb{E}[X|Y=y]=G'_{X|Y}(1|y).

我们知道全期望公式，即对于任意随机变量 X,Y，有 \mathbb{E}[Y]=\mathbb{E}[\mathbb{E}[Y|X]]，含义是“整体期望等于条件期望的期望”，PGF 与条件 PGF 的关联就在于全期望公式的另一写法：G_X(s)=\mathbb{E}[G_{X|Y}(s|Y)]，即整体 PGF 是条件 PGF 关于 Y 的混合平均；进一步，将上式按事件 A 分解，有 G_X(s)=\mathbb{P}(A)G_{X|A}(s)+\mathbb{P}(A^c)G_{X|A^c}(s).

举个例子，若 X\sim \operatorname{Poisson}(\lambda)，则 G_X(s)=e^{\lambda(s-1)}，因此，给定 X\ge 1 的条件 PGF 为 G_{X|X\ge 1}(s)=\dfrac{G_X(s)-\mathbb{P}(X=0)}{1-\mathbb{P}(X=0)}=\dfrac{e^{\lambda(s-1)-e^{-\lambda}}}{1-e^{-\lambda}}.

以下是 PGF 的一些推论及简略证明：

推论一：对于任意 n\ge 0，有 \mathbb{P}(X=n)=\frac{G_X^{(n)}(0)}{n!}.

证明：考虑对 G_X(s) 求 n 阶导，有 G_X^{(n)}(s)=\sum\limits_{k\ge n}k(k-1)\dots(k-n+1)p_ks^{k-n}，令 s=0，则仅有 k=n 时该式非 0，因此 G_X^{(n)}(0)=n!p_n，证毕。

推论二：若 \mathbb{E}[X]<\infty，则 \mathbb{E}[X]=G'_X(1^-)，进一步，若 \mathbb{E}[X^2]<\infty，则 \operatorname{Var}(X)=G''_X(1^-)+G'_X(1^-)-[G'_X(1^-)]^2.

证明：显然有 G'_X(s)=\sum\limits_{k\ge 1}kp_ks^{k-1}=\sum\limits_{k\ge 0}kp_ks^{k-1},G''_X(S)=\sum\limits_{k\ge 2}k(k-1)p_ks^{k-2}=\sum\limits_{k\ge 0}k(k-1)p_ks^{k-2}，对于一阶导，当 \mathbb{E}[X]=\sum\limits_{k\ge 0}kp_k<\infty 时，令 s\uparrow 1 则有 G'_X(1^-)=\sum\limits_{k\ge 0}kp_k=\mathbb{E}[X].

对于二阶导，有 G''_X(s)=\sum_{k\ge 0}k^2p_ks^{k-2}-\sum_{k\ge 0}kp_ks^{k-2}，当 \mathbb{E}[X^2]<\infty时，令 s\uparrow 1 则有 G''_X(1^-)=\mathbb{E}[X^2]-\mathbb{E}[X]，即 \mathbb{E}[X^2]=G''_X(1^-)+\mathbb{E}[X]，代入得 \operatorname{Var}(X)=\mathbb{E}[X^2]-(\mathbb{E}[X])^2=G''_X(1^-)+G'_X(1^-)-[G'_X(1^-)]^2.

更一般的，G_X^{(n)}(1^-)=\mathbb{E}[X(X-1)\dots(X-n+1)] 给出了 n 阶阶乘矩，期望与方差公式即为该式在 n=1,2 时的特例。

推论三：若 X_1,X_2,\dots,X_n 相互独立，且各自取值于 \mathbb{N}，则 G_{X_1+X_2+\dots+X_n}(s)=G_{X_1}(s)G_{X_2}(s)\dots G_{X_n}(s).

证明：考虑 n=2，设 X,Y 独立，则 s^X,s^Y 同样独立，因此 G_{X+Y}(s)=\mathbb{E}[s^{X+Y}]=\mathbb{E}[s^Xs^Y]=\mathbb{E}[s^X]\mathbb{E}[s^Y]=G_X(s)G_Y(s)，归纳证明即可，这说明独立随机变量之和的分布卷积，在 PGF 层面变成了普通乘法。

应用：若 X_i\sim \operatorname{Binomial}(n_i,p) 且相互独立，则 G_{X_i}(s)=(q+ps)^{n_i}，因此 X_1+X_2+\dots+X_m 的 PGF 为 \prod\limits_{i=1}^m (q+ps)^{n_i}=(q+ps)^{\sum_i n_i}，从而 X_1+X_2+\dots+X_m\sim \operatorname{Binomial}(\sum_i n_i,p).

推论四：设 q_n=\mathbb{P}(X>n) 为尾概率，序列 q_n 的普通生成函数为 T(s)=\sum\limits_{n\ge 0}q_ns^n，则满足 T(s)=\dfrac{1-G_X(s)}{1-s}，其中 |s|<1.

证明：显然有 q_n=\mathbb{P}(X>n)=\sum\limits_{k>n} p_k，代入有 T(s)=\sum\limits_{n\ge 0}q_ns^n=\sum_{k\ge 1}p_k\sum\limits_{n=0}^{k-1}s^n=\sum\limits_{k\ge 1}p_k\dfrac{1-s^k}{1-s}=\dfrac{1-G_X(s)}{1-s}.

由此可得 \mathbb{E}[X]=T(1^-)，尾概率的高阶矩也可由 T(s) 在 s=1 处的导数给出，常被用于离散时间马尔可夫链中的首达时分析。

除上述推论外，PGF 还有更加牛逼的应用：

一.复合函数

上述推论三提到独立随机变量和的 PGF 是乘积，但更一般的情形是随机数量的随机变量之和，即 S=X_1+X_2+\dots+X_N，其中 N 本身也是随机变量，称 S 为随机和，且 N,X_1,X_2\dots,X_N 相互独立。

据此有推论：若 X_i 独立同分布，其 PGF 为 G_X(s)；N 的 PGF 为 G_N(s)，则随机和 S 的 PGF 为函数复合，即 G_S(s)=G_N(G_X(s)).

证明：由全期望公式，对 S 的条件期望求外层期望，有 G_S(s)=\mathbb{E}[s^S]=\mathbb{E}[\mathbb{E}[s^{X_1+X_2+\dots+X_N}\mid N]]。给定 N=n 时，S 是 n 个独立同分布变量之和，其条件 PGF 为 [G_X(s)]^n，于是 G_S(s)=\sum\limits_{n\ge 0}\mathbb{P} (N=n) [G_X(s)]^n=G_N(G_X(s)).

由此可以推出复合泊松分布 G_S(s)=\exp(\lambda(G_X(s)-1))，同理对 G_S(s)=G_N(G_X(s)) 在 s=1 处分别求一阶导和二阶导可以得到随机和的期望 \mathbb{E}[S]=\mathbb{E}[N]\mathbb{E}[X] 与方差 \operatorname{Var}(S)=\mathbb{E}[N]\operatorname{Var}(X)+\operatorname{Var}(N)(\mathbb{E}[X])^2.

二.不动点定理

首先我们需要了解 Galton-Watson 分支过程：从第 0 代的一个祖先个体开始，设 Z_n 表示第 n 代的个体数量，第 n 代的每个个体都独立的产生后代，且均服从相同的后代分布 \{p_k\}_{k\ge 0}，其中 p_k 为单个个体产生 k 个后代的概率，问题是求这个种群最终灭绝的概率。

考虑设 G(s)=\sum\limits_{k\ge 0}p_ks^k 是后代分布的 PGF，则定理内容是：灭绝概率 \eta 是方程 G(s)=s 在区间 [0,1] 上的最小根， 并且若平均后代数 \mu=G'(1^-)\le 1，则 \eta=1，否则存在正概率永不灭绝，即 \eta<1.

考虑证明。令 G_n 为 Z_n 的 PGF，的 Z_{n+1} 是 Z_n 个独立后代的综合，由复合规则得 G_{n+1}(s)=G_n(G(s))=G(G_n(s))，而灭绝概率 \eta_n=\mathbb{P}(Z_n=0)=G_n(0)，于是 \eta_{n+1}=G_{n+1}(0)=G(G_n(0))=G(\eta_n)，根据 \eta_0=0 以及 G 在 [0,1] 上连续且单调不减，令 n\rightarrow \infty 则有 \eta=G(\eta)，因此证得灭绝概率 \eta 是该 PGF 的不动点。

发现方程 G(s)=s 可能有多解，考虑设 r 为 G(s)=s 在 [0,1] 上的任意解，则有 \eta_0=0\le r 且若 \eta_n\le r 则 \eta_{n+1}=G(\eta_n)\le G(r)=r，因此灭绝概率 \eta 还是该 PGF 在 [0,1] 上最小的不动点。

考虑 \eta 与 \mu 的关系，令 h(s)=G(s)-s，则 h(0)=p_0>0,h(1)=0,h''(s)=G''(s)>0(s>0)，因此 h 在 [0,1] 上严格凸性，则 h 在 (0,1) 上至多有一个根，是否有根取决于 h 在 s=1 处的左导数 h'(1^-)=G'(1^-)-1=\mu-1.

证明完毕后我们不妨思考其收敛速度，即 \mu>1 时，\eta_n\rightarrow\eta 的速度如何。我们在不动点附近线性化，即 \eta_{n+1}-\eta=G(\eta_n)-G(\eta)\approx G'(\eta)(\eta_n-\eta)，由于 G 严格凸，G(0)=p_0>0,G(\eta)=\eta 且 \eta<1，在 \eta 处 G 从上方穿过对角线，因此有 G'(\eta)<1，于是 |\eta_n-\eta|\approx C[G'(\eta)]^n，即几何收敛，收敛速度由 G'(\eta)\in(0,1) 控制。

三.连续性定理

设 \{X_n\} 是一列取值于 \mathbb{N} 的随机变量，其 PGF 为 G_{X_n}(s)=\mathbb{E}[s^{X_n}]，概率质量函数为 p_n(k)=\mathbb{P}(X_n=k)，又设 X 是一个取值于 \mathbb{N} 的随机变量，PGF 为 G_X(s)，概率质量函数为 p(k)=\mathbb{P}(X=k).

则以下两个命题等价：

  1. 分布收敛，即对于每个固定的 k=0,1,2,\dots，都有 \lim_{n\rightarrow\infty}p_n(k)=p_k.
  2. PGF 逐点收敛，即对于每个固定的 s\in[0,1]，都有 \lim_{n\rightarrow\infty} G_{X_n}(s)=G_X(s)

换句话说，一列离散分布收敛于一个极限离散分布，当且仅当其对应的 PGF 在 [0,1] 上逐点收敛。

考虑分开证明必要性和充分性：

理解 PGF 连续性定理的一个有效视角，是将其与概率论中更一般的特征函数连续性定理（Lévy 连续性定理）进行对照。

对于实值随机变量，特征函数 \varphi(t)=\mathbb{E}[e^{itX}] 的逐点收敛，再加上极限函数在 t=0 处的连续性，才能保证分布弱收敛。PGF 连续性定理之所以在形式上更简洁（无需额外的连续性条件），是因为它的适用范围被限定在非负整数值随机变量上。

该定理最典型的应用之一是为二项分布的泊松逼近提供证明。设 X_n\sim \operatorname{Binomial}(n,p_n)，且有 np_n\rightarrow\lambda>0，其 PGF 为 G_{X_n}(s)=(1-p_n+p_ns)^n.

当 n\rightarrow\infty 时，根据代数变形显然有 G_{X_n}(s)=\left(1+\dfrac{\lambda(s-1)}{n}+O\left(\dfrac{1}{n}\right)\right)^n\rightarrow e^{\lambda(s-1)}，而 e^{\lambda(s-1)} 恰好是参数为 \lambda 的泊松分布的 PGF，由于 PGF 逐点收敛到泊松分布的 PGF，根据连续性定理，即可断定 X_n 的概率质量函数逐点收敛于泊松分布的概率质量函数，即 \dbinom{n}{k}p_n^k(1-p_n)^{n-k}\rightarrow \dfrac{e^{-\lambda}\lambda^k}{k!}，这正是泊松逼近的严格数学表述。

这似乎扯得有点远了，我们回归 PGF 在 OI 上的应用，即开头提到的歌唱王国。

设 f_i 表示最终长度为 i 的概率，F(x)=\sum_{i\ge 0} f_ix^i，g_i 表示长度为 i 时还未结束的概率，G(x)=\sum_{i\ge 0} g_ix^i，所求即为 \mathbb{E}[x]=F'(1).

于是我们容易得到 F(x)+G(x)=xG(x)+1，含义是到第 i 位的概率等于到第 i+1 位还未结束的概率，则 F'(x)+G'(x)=xG'(x)+G'(x)，因此 F'(1)=G(1)，于是转化为求 G(1).

设字符串长度为 m，字符集大小为 n 以及目标串的 Border 长度集合 B，则考虑一个未停止的序列，在其末尾拼接上完整目标串必定结束，但拼接过程中有可能因为出现 Border 而提前结束，因此有 G(x)(\frac{x}{n})^m=\sum_{i\in B}F(x)(\frac{x}{n})^{m-i}，代入 x=1 得到 \mathbb{E}[x]=G(1)=\sum_{i\in B} n^i，时间复杂度 O(tm).