前言

标题致敬某神仙选手。

概率生成函数

定义

对于取值范围为非负整数的离散型随机变量 $X$,我们定义其 概率生成函数(PGF)为数列 $\langle \operatorname{Pr}[X=0], \operatorname{Pr}[X=1],\cdots\rangle$ 的普通生成函数,即:

$$ f(x) = \sum_{n\ge 0}\operatorname{Pr}[X = n]x^n $$

代入 $x = 1$,我们可以得到一个基本性质:

$$ f(1) = \sum_{n\ge 0}\operatorname{Pr}[X = n] = 1 $$

我们对 $f$ 求导,可以得到:

$$ f'(x) = \sum_{n\ge 1}n \operatorname{Pr}[X = n]x^{n-1} $$

代入 $x = 1$,可得:

$$ f'(1) = \sum_{n\ge 1}n \operatorname{Pr}[X = n] = \operatorname{E}[X] $$

即 $f'(1)$ 的值为 $X$ 的 期望

以此类推,我们可以得到:

$$ f^{(k)}(1) = \operatorname{E}[X^{\underline k}] $$

例 1

(Luogu P1654)有一个长度为 $n$ 的序列,位置 $i$ 有 $p_i$ 的概率为 $1$,$1 - p_i$ 的概率为 $0$,求所有极长连续 $1$ 的长度立方之和的期望。

$1\le n\le 10^5$.

展开阅读题解

当然这题存在不用生成函数的做法,但是这里不作提及。

记 $f_i(x)$ 表示从 $i$ 开始,往前的 $1$ 的连续段的期望长度的概率生成函数,由期望的线性性可知,答案为(注意这里要保证每个连续段是在最后一个位置被统计的,也就是下个位置必须是 $0$):

$$ \sum_{i=1}^n (1 - p_{i+1})(f_i'(1) + 3f_i''(1) + f_i'''(1)) $$

问题来了,如何求 $f_i'(1),f_i''(1),f_i'''(1)$ 呢?我们通过考虑当前位置是否为 $1$,可以得到:

$$ f_i(x) = 1 - p_i + p_i\cdot xf_{i-1}(x) $$

故:

$$ \begin{aligned} f_i'(x) & = p_i(xf_{i-1}'(x) + f_{i-1}(x)) \\ f_i''(x) & = p_i(xf_{i-1}''(x) + 2f_{i-1}'(x)) \\ f_i'''(x) & = p_i(xf_{i-1}'''(x) + 3f_{i-1}''(x)) \end{aligned} $$

全部代入 $x = 1$,得(注意 $f_{i-1}(1) = 1$):

$$ \begin{aligned} f_i'(1) & = p_i(f_{i-1}'(1) + 1) \\ f_i''(1) & = p_i(f_{i-1}''(1) + 2f_{i-1}'(1)) \\ f_i'''(1) & = p_i(f_{i-1}'''(1) + 3f_{i-1}''(1)) \end{aligned} $$

递推一下就可以做到 $\mathcal O(n)$ 的复杂度。

Bonus:此题改成求 $k$ 次方和的期望,对 $998244353$ 取模,$n$ 范围不变,$1\le k\le 100$.

例 2

(CTSC 2006)给定一个长度为 $m$ 的字符串 $s$,字符集大小为 $n$,每次从字符集中等概率随机生成一个字符加入到初始为空的序列的最末端,当序列中出现子串 $s$ 的时候停止,求序列的期望长度。

$1\le n,m\le 10^5$.

展开阅读题解

此题同样存在一个不用生成函数的做法,但这里不作提及。

考虑设 $f(x)$ 表示结束时长度的概率生成函数,$g(x)$ 表示到长度为 $i$ 时还未结束的概率 $\langle p_i \rangle$ 的普通生成函数。

对于一个还未结束的序列,加入一个元素,可能结束,也可能不结束,但一定非空,故:

$$ xg(x) = f(x) + g(x) - 1 $$

两边同时求导并代入 $x = 1$,得:

$$ \begin{aligned} g(x) + xg'(x) & = f'(x) + g'(x) \\ g(1) & = f'(1) \end{aligned} $$

(事实上,这个式子有个不用生成函数的推法,大家可以想一想)

对于一个还未结束的序列,加入一整个 $s$,必然结束,但可能提前结束,此时我们加入了 $s$ 的一个前缀,它恰好是 $s$ 的某个后缀,故此时我们加入的一定是 $s$ 的一个 Border。

记 $a_i$ 表示 $s$ 的前 $i$ 个字符组成的前缀是否是 $s$ 的后缀,则有(注意 $f(x)$ 中已经暗含了“匹配成功了”的信息,所以只需要满足这个前缀是一个 Border 就好了):

$$ g(x)\left(\frac 1nx\right)^m = \sum_{i=1}^m a_i f(x)\left(\frac 1nx\right)^{m-i} $$

代入 $x = 1$,容易得到:

$$ f'(1) = g(1) = \sum_{i=1}^m a_in^i $$

用 KMP 求得 $a_i$,然后这道题就做完了。

Bonus:SDOI 2017 硬币游戏。

例 3

一个有趣的概率小问题)有一个 $n$ 面的质地均匀的骰子,有一个计数器,初始为 $0$,每一次投掷骰子时,依次进行以下步骤:

  1. 若扔中偶数,计数器 $+1$.
  2. 若扔中奇数,计数器置 $0$.
  3. 若扔中 $n$,结束扔骰子的过程。

求结束时计数器上数的期望。

$1\le n\le 10^9$.

展开阅读题解

这是道比较有意思的题。

依照先前的套路,我们应当设概率来做,但是这道题中我们发现,概率之间的关系是难以用简单的式子来描述的。

于是我们考虑用“期望次数”的 OGF 来进行操作。(期望生成函数,EGF

设 $p_i$ 表示“计数器值为 $i$,且此时结束”这个事件发生的期望次数(容易发现,在任何一整段掷骰子的过程中,这个事件只会发生恰好一次,所以 $p_i$ 实际上也为该事件发生的概率),$q_i$ 表示“计数器值为 $i$,且此时还未结束”这个事件发生的期望次数,它们的生成函数分别为 $f(x)$ 和 $g(x)$。

于是,我们可以得到:

$$ f(x) + g(x) = \frac 12(x\cdot g(x) + g(1)) + 1 $$

其中,左侧的意义显然是“计数器值为 $i$”这件事发生的期望次数。

右侧前半部分实际上是在枚举当前掷的骰子是奇数还是偶数,若是奇数,则先前所有为“计数器为 $i$”的事件发生之后都将变为 $0$,所以就求个和($g(1)$)加到 $x^0$ 的系数上。

而右侧后半部分的 $1$ 表示最开始就发生了一个事件“计数器值为 $0$,且此时还未结束”(最开始的这个事件是唯一一个不由掷骰子所决定的事件,故不会在前面被统计)。

然后,根据是否掷出 $n$,我们可以得到:

$$ f(x) = \frac xn\cdot g(x) $$

代入 $x = 1$,以及求导后代入 $x = 1$,我们可以得到:

$$ \frac 1n\cdot g(1) = f(1) = 1 \Rightarrow g(1) = n \\ f'(1) = \frac 1n\cdot g'(1) + 1 $$

由 $g(1) = n$,故:

$$ f(x) + g(x) = \frac 12(x\cdot g(x) + n) + 1 $$

将 $g(x)$ 移到右边后左右同时求导,可得:

$$ f'(x) = \frac 12((x-2)g'(x) + g(x)) $$

再代入 $x = 1$:

$$ f'(1) = \frac 12((x-2)g'(1) + n) $$

我们已经成功有了两个方程,容易解得:

$$ \left\{\begin{aligned} g'(1) & = \frac {n(n-2)}{n+2}\\ f'(1) & = \frac {2n}{n + 1}\\ \end{aligned}\right. $$

容易发现,$f'(1)$ 即为所求。

参考文献

最后修改:2021 年 03 月 14 日 08 : 17 PM