概率生成函数PGF
TLE_Automat
·
·
算法·理论
对于离散的概率生成函数
\begin{aligned}
f_X(x) &= \sum_{k} P(X=k)x^{k} \\
E(X) &= \sum_{k}k\cdot P(X=k) = f'_{X}(1) \\
E(X^2) &= \sum_{k} k^{2}P(X=k) = \sum_{k}[k(k - 1) + k]P(X=k) = f''_{X}(1) + f'_{X}(1)
\end{aligned}
考虑怎么求 E(x^{n})，由于
\begin{aligned}
f_{X}(e^{x}) &= \sum_{k}P(X=k)e^{kx} \\
&= \sum_{k}P(X=k)\sum_{n}\frac{(kx)^n}{n!} \\
&= \sum_{n}\frac{x^{n}}{n!}\sum_{k} P(X=k)k^{n} \\
&= \sum_{n}\frac{E(X^{n})}{n!}x^{n}
\end{aligned}
这称为随机变量 X 的矩母函数，由此可见 E(x^{n}) = n![x^{n}]f_{X}(e^{x})，考虑怎么求 f_X(e^{x}) 的各项系数。
若 f_{X}(x) 是无限项的，需要求其封闭形式；若 f_{X}(x) 是有限项的，考虑求
\begin{aligned}
\sum_{n}E(X^{n})x^{n} &= \sum_{n}\sum_{k} P(X=k)k^{n}x^{n} \\
&= \sum_{n}\sum_{k}f_{k}k^{n}x^{n} \\
&= \sum_{k}f_{k}\sum_{n}(kx)^{n} \\
&= \sum_{k} \frac{f_{k}}{1 - kx}
\end{aligned}
使用分治 FFT 维护分子分母，最后多项式求逆即可求出，时间复杂度 O(n\log^{2}n)。
下面我们来一道例题，一个歌唱王国的加强版。
- 字符集为 \Sigma，打出第 i 个字符的概率为 p_{i}，给出一个字符串 s，求后缀第一次出现字符串 s 的期望打字次数 E(s)。
令 f_{k} 代表打了 k 个字符还没停的概率，g_k 代表打了 k 个字符恰好停的概率。
由于 f_{k} = \sum_{j=k+1}g_{j} = f_{k + 1} + g_{k + 1}，即
\begin{aligned}
1 + xf(x) = f(x) + g(x)\ \ \ \ \ \ (1)
\end{aligned}
考虑打了 p 个字符还没停，并且钦定在后面完整地打出一个字符串 t 的概率，用两种不同的形式表达，即
\begin{aligned}
f_{p} \prod_{i = 1}^{|t|}p_{t_{i}} = \sum_{k\in \text{border}(t)} g_{p+k}\prod_{i = k + 1}^{|t|}p_{t_{i}}
\end{aligned}
写成生成函数的形式，即
\begin{aligned}
f(x)\cdot x^{|t|}\prod_{i=1}^{|t|}p_{t_{i}} = g(x) \sum_{k\in \text{border}(t)} x^{|t|-k}\prod_{i=k+1}^{|t|}p_{t_{i}} \ \ \ \ \ (2)
\end{aligned}
将 (1) 式带入 (2) 式中，化简可得
\begin{aligned}
g(x) = \frac{\prod\limits_{i=1}^{|t|}p_{t_{i}}}{(1-x)\sum\limits_{k\in \text{border(t)}}x^{-k}\prod\limits_{i=k+1}^{|t|}p_{t_i} + \prod_{i=1}^{|t|}p_{t_{i}}}
\end{aligned}
求导带入 x=1 即可得到
\begin{aligned}
E(s) = g'(1) = \sum\limits_{k\in \text{border}(t)}\prod_{i=1}^{k}\frac{1}{p_{t_{i}}}
\end{aligned}