概率生成函数PGF

对于离散的概率生成函数

\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}

文章操作