如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
对于离散型随机变量 $X$，其值域为非负整数，定义其 $\text{PGF}$ 为
\[F(z)=\sum\limits_{i=0}^{\infin}P(X=i)z^i\]注意到我们有
\[F(1)=\sum\limits_{i=0}^{\infin}P(X=i)=1\\ F^{\prime}(1)=\sum\limits_{i=1}^{\infin}P(X=i)i=E(X)\\ F^{\prime\prime}(1)=\sum\limits_{i=2}^{\infin}P(X=i)i(i-1)=E(X(X-1))\\ \cdots\\ F^{(k)}(1)=\sum\limits_{i=k}^{\infin}P(X=i)i^{\underline k}=E(X^{\underline k})\]其实就是 $\text{OGF}$，我们对其定义了 $F(1)$ 这种运算。
例题
Dice
一个 $m$ 面的公平骰子，求
- 最后 $n$ 次结果相同就结束的期望次数
- 最后 $n$ 次结果全不同就结束的期望次数。
保证 $n,m\le 10^6$。
做法
- 最后 $n$ 次结果相同就结束的期望次数
设随机变量 $X$ 为结束时间，设其 $\text{PGF}$ 为 $F(z)$，设数列 $g_i$ 表示投掷 $i$ 次仍未结束的概率，设其 $\text{OGF}$ 为 $G(z)$。我们有
\[G(z)z+1=F(z)+G(z)\\\]即考虑再投掷一次骰子，此时可能结束也可能没结束。还有
\[G(z)\left(\frac 1mz\right)^n=\sum\limits_{i=1}^nF(z)\left(\frac 1mz\right)^{n-i}\]即考虑在未结束的序列后连续投掷 $n$ 个相同的结果，但可能未投掷 $n$ 个就已经结束了，所以枚举多出了多少个。
我们可以得到
\[G^{\prime}(z)z+G(z)=F^{\prime}(z)+G^{\prime}(z)\\ G^{\prime}(1)+G(1)=F^{\prime }(1)+G^{\prime}(1)\\ F^{\prime}(1)=G(1)\\ G(1)\left(\frac 1m\right)^n=\sum\limits_{i=1}^nF(1)\left(\frac 1m\right)^{n-i}\\ G(1)=\sum\limits_{i=1}^nm^i\\\]- 最后 $n$ 次结果全不同就结束的期望次数
基本和上面没区别，设随机变量 $X$ 为结束时间，设其 $\text{PGF}$ 为 $F(z)$，设数列 $g_i$ 表示投掷 $i$ 次仍未结束的概率，设其 $\text{OGF}$ 为 $G(z)$。我们有
\[G(z)z+1=F(z)+G(z)\\ G(z)\left(\frac{m^{\underline n}}{m^n}z^n\right)=\sum\limits_{i=1}^nF(z)\left(\frac{(m-i)^{\underline {n-i}}}{m^{n-i}}z^{n-i}\right)\\ F^{\prime}(1)=G(1)=\sum\limits_{i=1}^n\frac{m^i}{m^{\underline i}}\][CTSC2006] 歌唱王国
一个长为 $n$ 的字符串，字符集大小为 $m$，求初始有一个空字符串，每次等概率随机一个字符加到后面，期望对=多少次产生给定字符串。
做法
设随机变量 $X$ 为结束时间，设其 $\text{PGF}$ 为 $F(z)$，设数列 $g_i$ 表示随 $i$ 次仍未结束的概率，设其 $\text{OGF}$ 为 $G(z)$，仍然有 $F^{\prime}(1)=G(1)$，设 $a_i$ 表示 $i$ 是否为 Border。
\[G(z)\left(\frac{1}{m^n}z^n\right)=\sum\limits_{i=1}^na_iF(z)(\frac{1}{m^{n-i}}z^{n-i})\\ G(1)=\sum\limits_{i=1}^na_im^i\][ZJOI2013] 抛硬币
一个长为 $n$ 的字符串 $s$，字符集为 $01$，求初始有一个空字符串，每次以 $p$ 的概率将 $0$ 加到后面，以 $1-p$ 的概率将 $1$ 加到后面，期望多少次产生给定字符串。
做法
设随机变量 $X$ 为结束时间，设其 $\text{PGF}$ 为 $F(z)$，设数列 $g_i$ 表示随 $i$ 次仍未结束的概率，设其 $\text{OGF}$ 为 $G(z)$，仍然有 $F^{\prime}(1)=G(1)$，设 $a_i$ 表示 $i$ 是否为 Border，$P(s)$ 表示随机出 $s$ 的概率。
\[G(z)\left(P(s[1:n])z^n\right)=\sum\limits_{i=1}^na_iF(z)(P(s[i+1:n])z^{n-i})\\ G(1)=\sum\limits_{i=1}^na_i\frac{P(s[i+1:n])}{P(s[1:n])}=\sum\limits_{i=1}^na_i\frac 1{P(s[1:i])}\]一个有趣的概率小问题
一个 $n$ 面的骰子。有个初始为 $0$ 的计数器，每次扔骰子，如果结果是奇数，那么计数器清零，否则计数器加 $1$，并且如果结果是 $n$ 则在加 $1$ 后结束，问结束时计数器的期望。 保证 $n$ 是偶数。
做法
设 $X$ 为结束时计数器的值，其 $\text{PGF}$ 为 $F(z)$，设 $g_i$ 为结束前计数器 $=i$ 的期望次数，其 $\text{OGF}$ 为 $G(z)$，我们有
\[\frac{G(z)z}{2}+\frac{G(1)}{2}+1=F(z)+G(z)\\\]左侧表示有一半概率 $+1$，有一半概率归零，$+1$ 表示最初为 $0$，右侧表示计数器 $=i$ 的总期望次数，包括结束前和结束时。又有
\[F(z)=\frac {G(z)z}{n}\\\]即考虑下一次是 $n$ 的概率是 $\frac 1n$，由这个式子也可以知道 $G(1)=n$，于是有
\[F^{\prime}(z)=\frac{G^{\prime}(z)z+G(z)}{n}\\ F^{\prime}(1)=\frac{G^{\prime}(1)+n}{n}\\ G^{\prime}(1)=nF^{\prime}(1)-n\]对第一个式子求导，有
\[\frac{G^{\prime}(z)z+G(z)}{2}=F^{\prime}(z)+G^{\prime}(z)\\ \frac{G^{\prime}(1)+n}{2}=F^{\prime}(1)+G^{\prime}(1)\\ \frac{nF^{\prime}(1)-n+n}{2}=F^{\prime}(1)+nF^{\prime}(1)-n\\ F^{\prime}(1)=\frac{2n}{n+2}\][SDOI2017] 硬币游戏
给定 $n$ 个长为 $m$ 的由 $01$ 组成的序列 $s_i$，同时每次掷一颗均匀的双面骰子，求每个序列最先被掷出的概率。
做法
设 $f_{i,j}$ 表示首次出现的序列为 $i$，且长度为 $j$ 的概率，设 $F_i(z)$ 为其 $\text{OGF}$，答案就是 $F_i(1)$，有 $\sum\limits_{i=1}^nF_i(1)=1$。
设 $g_i$ 表示长为 $i$ 的序列未结束的概率，设 $G(z)$ 为其 $\text {OGF}$。
设 $a_{i,j,k}$ 表示 $s_i[1:k]$ 是否等于 $s_j[m-k+1,m]$。
我们有 \(\forall i,G(z)\frac{z^m}{2^m}=\sum\limits_{j=1}^n\sum\limits_{k=1}^ma_{i,j,k}F_j(z)\frac{z^{m-k}}{2^{m-k}}\)
将 $1$ 代入
\[\forall i,G(1)=\sum\limits_{j=1}^nF_j(1)\sum\limits_{k=1}^ma_{i,j,k}2^k\\ \sum\limits_{i=1}^nF_i(1)=1\]一共 $n+1$ 条等式，$n+1$ 个未知数，直接高斯消元即可。