PGF 学习笔记
Cherished
·
·
个人记录
前言
众所周知 PGF 是 useless，但是我最喜欢 useless 了，所以来学了一下。
咱是论文的搬运工。
我们使用 \operatorname{Pr}(X=i) 表示 X=i 的概率。
这样对于一个离散随机变量 X，其在非负整数集 N 上的 PGF 为：
F(z)=E(z^X)=\sum_{i=0}^{\infty}{\operatorname{Pr}(X=i)z^i}
可以发现一些结论：（\operatorname{Var} 表示方差）
\begin{aligned}
F(1)&=\sum_{i=0}^{\infty}{\operatorname{Pr}(X=i)}=1 \\
F'(z)&=\sum_{i=0}^{\infty}{\operatorname{Pr}(X=i)iz^{i-1}} \\
E(x)&=F'(1) \\
\operatorname{Var}(X)&=F''(1)+F'(1)-(F'(1))^2
\end{aligned}
通常来说概率生成函数解决的都是类似于，每次随机一个数添加在序列后面，在到达某条件的时候序列终止，求序列结束时的期望长度。
这些问题的传统做法一般都是将到达某种结束状态的前缀设为未知数，之后解方程，或是根据式子的特殊性求解。
对于这种问题我们通常都列出两个方程。
- 在未结束状态后面操作一次
- 强制添加一些状态使得直接结束，但是注意到可能已经提前结束了
下面是一些例题：
歌唱王国
每次在 B 序列末尾添加一个 [1,m] 中的随机变量，当且仅当序列 A 是 B 的子串时，就停止操作，求 B 序列期望长度。(A 的长度为 L)
(a_i 表示 A 序列是否有长度为 i 的 border)
\begin{aligned}
F(x)+G(x)&=xG(x)+1 \\
G(x)(\frac{1}{m}x)^L&=\sum_{i=1}^{n}{a_iF(x)(\frac{1}{m}x)^{L-i}}
\end{aligned}
对第一个式子求导并带入 x=1 可以得到，F'(1)=G(1)。
直接将 x=1 带入第二个式子可以得到，G(1)=\sum_{i=1}^{n}{a_im^i}。
还可以去看看 [SDOI2017] 做法是大同小异的。
Dice
一个 m 面骰子，连续 n 次相同的期望次数，和连续 n 次都不同的期望次数。
第一问
F(x)+G(x)=xG(x)+1 \\
G(x)(\frac{1}{m}x)^{n-1}=\sum_{i=1}^{n}{F(x)(\frac{1}{m}x)^{n-i}}
直接可以解得 F'(1)=\frac{m^n-1}{m-1}。
第二问
F(x)+G(x)=xG(x)+1 \\
G(x)(\frac{1}{m}x)^{n}\frac{m!}{(m-n)!}=\sum_{i=1}^{n}{F(x)(\frac{1}{m}x)^{n-i}\frac{(m-i)!}{(m-n)!}}
解得 F'(1)=\sum_{i=1}^{n}{m^i\frac{(m-i)!}{m!}}。
趣题
设 $G$ 为计数器等于 $i$ 的期望次数，可以列出
$$
F(x)+G(x)=G(x)\frac{x}{2}+\frac{G(1)}{2}+1 \\
F(x)=G(x)\frac{x}{n}
$$
之后就是简单的解方程，可以得到 $F'(1)=\frac{2n}{n+2}$。
### 拓展
让我们再回到歌唱王国这个问题上。
如果我们将问题改成求长度平方的期望怎么做。
可以发现我们给第一个式子求两次导可以得到：
$$
F''(1)=2G'(1)
$$
给第二个式子求导可以得到：
$$
G'(1)=\sum_{i=1}^{L}{a_im^i(F'(1)-i)}
$$
我们也可以进一步拓展就可以得到：
$$
F^{(k)}(1)=k\sum_{i=1}^{L}{a_im^i\sum_{j=0}^{k-1}{(-1)^j{k-1\choose j}\frac{(i+j-1)!}{(i-1)!}F^{(k-1-j)}(1)}}
$$