概念
若 \(X\) 为非负整数集 \(\mathbb{N}\) 上的离散随机变量，其满足 \(\text{Pr}(X=i)=a_i\)，则称 \(a_n\ (n \in \mathbb{N})\) 的生成函数为 \(X\) 的概率生成函数，得：
因为 \(X\) 为非负整数集 \(\mathbb{N}\) 上的离散随机变量，所以有：
对 \(F(z)\) 求导，得：
得 \(X\) 的期望为：
得 \(X\) 的方差为：
应用
[CTSC2006] 歌唱王国
给定长为 \(m\) 的序列 \(A\)，每次等概率随机一个 \(1\) 到 \(n\) 的数加到初始为空的序列 \(B\) 的末尾，当 \(A\) 为 \(B\) 的子串时，停止随机，求序列 \(B\) 的期望长度。链接
\(m \leqslant 10^5\)
设 \(f_i\) 为 \(B\) 长度为 \(i\) 时停止的概率，\(g_i\) 为 \(B\) 长度为 \(i\) 时未停止的概率，分别得概率生成函数 \(F(x)\) 和普通生成函数 \(G(x)\)，所求即为 \({F}'(1)\)。
设 \(a_i\) 表示 \(A[1,i]\) 是否为 \(A\) 的 \(\text{border}\)，其取值为 \(0\) 或 \(1\)，得：
第一个式子为未停止时往后加一个数字，其可能停止，也可能未停止，加 \(1\) 是 \(B\) 为空的情况。第二个式子是向未停止的序列 \(B\) 直接加上序列 \(A\)，其一定会停止，但发现不一定要全部加上序列 \(A\)，这里还需考虑 \(\text{border}\)。
对第一个式子求导并代入 \(x=1\) 得：
将 \(x=1\) 代入第二个式子得：
因此有 \({F}'(1)=\sum\limits_{i=1}^ma_in^i\)，用 \(KMP\) 即可 \(O(m)\) 求解。
[SDOI2017] 硬币游戏
给定 \(n\) 个长度为 \(m\) 的 \(01\) 序列 \(A_i\)，序列互不相同，每次等概率随机 \(0\) 和 \(1\) 加到初始为空的序列 \(B\) 的末尾，当有 \(A_i\) 为 \(B\) 的子串时停止，对于每个 \(i\) 求出因其停止的概率。链接
\(1 \leqslant n, m \leqslant 300\)
设 \(f_{i,j}\) 为 \(B\) 长度为 \(j\) 时因 \(i\) 停止的概率，\(g_i\) 为 \(B\) 长度为 \(i\) 时未停止的概率，分别得概率生成函数 \(F_i(x)\) 和普通生成函数 \(G(x)\)，所求即为 \(F_i(1)\)。
设 \(a_{i,j,k}\) 表示 \(A_i\) 长度为 \(k\) 的前缀是否和 \(A_j\) 长度为 \(k\) 的后缀相等，其取值为 \(0\) 或 \(1\)，得：
和上一题一样，化简得：
注意到：
用高斯消元即可 \(O(n^3)\) 求解。