概率与期望

前言

从前有一个屑到要被淘汰的菜 Oier（其实就是我），他写了一个博客叫“浅谈数学期望”。然后好巧不巧在某一次更新博客的时候以前的文章全部被覆盖了，因为没有存笔记所以直接全部消失。这个人想着算了，覆盖掉就覆盖掉吧，鬼才会写概率和期望的博客。

半年后的今天，这个死鬼居然补起了学习笔记，好巧不巧，正好就有概率和期望。（我：WDNMD）

所以今天来写一波概率和期望的笔记。学长讲的时候都是以例题为主，顺带就把在洛谷上平均难度都是冷色系的概率 DP 一起水过去了，差点让我没跟上。所以这一次仔细写一写。

概率

概率，都不陌生，凡是有初中数学基础（好像是小学？）的都不会不知道什么是概率。

概率，亦称“或然率”，它是反映随机事件出现的可能性大小。随机事件是指在相同条件下，可能出现也可能不出现的事件。例如，从一批有正品和次品的商品中，随意抽取一件，“抽得的是正品”就是一个随机事件。设对某一随机现象进行了 $n$ 次试验与观察，其中 $A$ 事件出现了 $m$ 次，即其出现的频率为 $\frac{m}{n}$。经过大量反复试验，常有 $\frac{m}{n}$ 越来越接近于某个确定的常数（此论断证明详见伯努利大数定律）。该常数即为事件 $A$ 出现的概率，常用 $\operatorname{P}(A)$ 表示。（摘自百度）

举几个简单的例子，投一个骰子，$6$ 朝上的概率是 $\frac{1}{6}$，朝上的数字是奇数的概率是 $\frac{1}{2}$，是自然数的概率是 $1$，是负数的概率是 $0$。

至于穷举法树状图法表格法频率法计算法求概率，这篇文章不是数学课讲义，显然没必要赘述。

期望

期望好像不是初中的东西，简单提一下（其实是重点啊喂）

在概率论和统计学中，数学期望（mean）（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。
需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。期望值是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合里。（摘自百度）

期望就是这件事所有的结果（用一个数值表示）乘上它对应的概率，然后全部加起来。说的有点玄乎，举个例子看看：抛一个骰子，朝上的一面的数字期望是多少？

显然数字可能是 $1,2,3,4,5,6$，对应的概率都是 $\frac{1}{6}$，因此朝上的一面期望值是：

$1\times\dfrac{1}{6}+2\times\dfrac{1}{6}+3\times\dfrac{1}{6}+4\times\dfrac{1}{6}+5\times\dfrac{1}{6}+6\times\dfrac{1}{6}=3.5$

引导例题：同时投两个骰子，朝上的一面数的和的期望。

每个骰子的数字都是 $1,2,3,4,5,6$，所以总和是 $[2,12]$，但是这些和出现的概率是均等的吗？但凡做过小学题都知道不均等。最原始的方法还是莫过于初中数学的表格法暴力枚举：
（为什么不用树状图法？只要你画得比这 $\LaTeX$ 做的表格还好看我就换）

一共有 $36$ 种情况，其中出现 $7$ 的次数最多。这能否代表 $7$ 一定是期望值呢？显然不能，例如一个骰子的时候，作为期望值的 $3.5$ 显然不可能出现。那这次的期望值是不是一定不在 $[2,12]$ 的整数范围内呢？还是计算一下比较好：

$2\times\dfrac{1}{36}+3\times\dfrac{2}{36}+4\times\dfrac{3}{36}+5\times\dfrac{4}{36}+6\times\dfrac{5}{36}+7\times\dfrac{6}{36}+8\times\dfrac{5}{36}+9\times\dfrac{4}{36}+10\times\dfrac{3}{36}+11\times\dfrac{2}{36}+12\times\dfrac{1}{36}=7$

（其实不约分不是因为容易理解而是因为这样方便复制粘贴 awa）

因此期望是 $7$。

从这里我们发现一个特点：一个骰子的时候期望是 $3.5$，骰子翻了一倍变成两个，期望值也翻了一倍。如果你是在没有什么事情去做，无聊到用枚举法算出三个骰子一起投的期望值，你会发现答案是 $10.5$，恰好是一个骰子的三倍，也恰好是投两个骰子和投一个骰子的期望总和。

因此我们得出几个很重要的性质：假设 $X,Y$ 都是随机变量（将一个随机事件的结果转化成数字的东西，比如投骰子是个随机事件，我把他转化成正面朝上的数字来记录它的结果），$X$ 的期望记作 $\operatorname{E}(X)$（这是官方记法，后续也是这么表示的），$k$ 是常数，则有：

1. $\operatorname{E}(kX)=k\cdot\operatorname{E}(X)$；
2. $\operatorname{E}(X+Y)=\operatorname{E}(X)+\operatorname{E}(Y)$；

除此之外，还有一个特别的性质：

3. 当 $X$ 和 $Y$ 相互独立时，有 $\operatorname{E}(XY)=\operatorname{E}(X)\cdot\operatorname{E}(Y)$。

特别的，对于常数 $k$，我们定义：$\operatorname{E}(k)=k$。

思考题

甲乙两人进行博弈游戏，每回合两个人都会选择 $1$ 或 $2$ 中的一个数。如果两人数字不一样，甲赢两元乙输两元；如果两人都选择 $2$，甲输三元乙赢三元；如果两人都选择 $1$，甲输一元乙赢一元。给甲确定一个选 $1$ 的概率，使得无论乙选数字用的什么概率，总的期望都是甲赢钱。

设甲选择 $1$ 的概率（即答案）为 $p$，乙选择 $1$ 的概率为 $q$。则有甲选 $2$ 的概率为 $1-p$，乙选 $2$ 的概率为 $1-q$。

同时选择 $1$ 的概率为 $pq$，对应甲的金钱变动是 $-1$。同时选择 $2$ 的概率是 $(1-p)(1-q)$，对应甲的金钱变动是 $-3$。如果甲出 $1$ 乙出 $2$，概率是 $p(1-q)$，金钱变动为 $2$。最后就是甲出 $2$ 乙出 $1$ 的情况，概率是 $q(1-p)$，变动为 $2$。总的期望就是：

$\begin{aligned} E & = -pq-3(1-p)(1-q)+2p(1-q)+2q(1-p) \\ & = -8pq+5p+5q-3 \\ & = (-8p+5)q+5p-3 \end{aligned}$

因为 $E$ 和 $q$ 无关，所以 $p=\dfrac{5}{8}$，带入原式得到 $E=\dfrac{1}{8}$。是正数，符合题意。

概率 DP

终于来到正题了，一般的概率 DP 不是让你求一个概率，而是求一个期望。而期望能进行 DP，就是因为期望满足上面几个性质，于是有可加性等性质。可以进行递推。

概率 DP 难在自己设计的状态不好进行转移。如果可以一拍脑袋想明白自己设计的状态怎么转移，实现上不会有太多的问题，毕竟一个正常的概率 DP 不会吃代码实现难度的，不然绝对黑题往上了。

DP 这种东西，没什么板子，都是灵活应变的。只好拿几个例题练手。考虑到代码实现都不难，而且本人比较懒，没有挂代码，但并不影响题解阅读。

例 1

链接。$n$ 个人排成一列，每秒钟最前面的人有 $p$ 的概率离开，$1-p$ 的概率不动。求 $t$ 秒后离开的人数期望。$n,t\leqslant 2\times 10^3$。

因为数据范围允许 $nt$ 乱搞，不妨就把题目的关键信息“人数”和“时间”当做状态。设 $f_{i,j}$ 表示考虑到了第 $i$ 个人，时间为第 $j$ 秒的期望人数。有两种情况：

1. 这个人在这一秒离开，由 $f_{i-1,j-1}$ 转移，概率为 $p$。
2. 这个人不离开，由 $f_{i,j-1}$ 转移，概率为 $(1-p)$。

因此有转移方程：

$f_{i,j}=p\times(f_{i-1,j-1}+1)+(1-p)\times f_{i,j-1}$

时间复杂度 $\operatorname{O}(nt)$。

例 2

链接。给定一颗有根树，每次操作等概率地选择一个未被删去的点并将以它为根的子树（包括节点本身）删除。求删除所有节点的期望次数。$n\leqslant 10^5$。

考虑到形式是树的形式给出，不好按照编号逐点递推。因为期望具有可加性（$\operatorname{E}(X+Y)=\operatorname{E}(X)+\operatorname{E}(Y)$），不妨考虑每一个点对答案的贡献。

对于一次操作如果 $i$ 号节点被删除，可能的情况是：

1. $i$ 节点本身被删除。
2. $i$ 节点的父亲被删除。
3. $i$ 节点的爷爷被删除。
4. $\cdots$
5. 根节点被删除。

假设根节点的深度为 $1$，每个节点的深度为 $dep_i$。因为选点是等概率的，所以这个点没有被删除，当且仅当它的所有祖先（和它自己）没有被删除。如果某次操作这个点删掉了，那么这个点刚好被选中并删除的概率，就是所有可能导致这个点删掉的点的个数的倒数，不难发现是 $\dfrac{1}{dep_i}$。这就是这个点对答案的贡献。

总的答案就是：

$ans=\sum_{i=1}^n\dfrac{1}{dep_i}$

时间复杂度显然 $\operatorname{O}(n)$。

例 3

链接。有一个空字符串，每次有 $p$ 的概率在字符串末尾追加一个字符 a，有 $1-p$ 的概率在字符串末尾追加一个字符 b。当出现 $k$ 个形如 ab 的子序列时结束。求最后形如 ab 的子串数量的期望。$k\leqslant 10^3$。

不难发现添加字符 a 对 ab 子序列的数量没有贡献。添加一个 b 会对其造成这个位置前面的 a 的数量那么多的贡献。不妨直接设 $f_{i,j}$ 表示有 $i$ 个 a，得到 j 个子序列的串数量期望。有两种转移：

1. 添加一个 a，子序列数不变，a 多了一个。可以转移到 $f_{i+1,j}$。
2. 添加一个 b，子序列数目多了 $i$ 个，可以转移到 $f_{i,i+j}$。

也就是：

$f_{i+1,j}\leftarrow f_{i+1,j}+f_{i,j}\times p$

$f_{i,i+j}\leftarrow f_{i,i+j}+f_{i,j}\times(1-p)$

边界条件显然是 $i+j\geqslant k$ 的时候。但是这个时候出现一个问题，有可能一直在往后面加 a。因此第一维的无穷大的。这就非常不好，不妨考虑当 $i=k$ 时，此时无论如何再加一个 b 都会直接结束。以此状态推边界条件：

$\begin{aligned} f_{k,j} & = p\times f_{k+1,j}+(1-p)\times(j+k) \\ & = p^2\times f_{k+2,j}+p\times(1-p)\times(j+k+1)+(1-p)\times(j+k) \\ & = \cdots \\ & = \sum_{i=0}^{\infty} p^i\times(1-p)\times(i+j+k) \\ & = \sum_{i=0}^{\infty} p^i\times i\times(1-p)+\sum_{i=0}^{\infty} p^i\times(1-p)\times(j+k) \\ \end{aligned}$

这里需要引入两个很重要的公式，引理的证明会放在文章末尾：

$\sum_{i=0}^{\infty} p^i=\dfrac{1}{1-p}$

$\sum_{i=0}^{\infty} p^i\times i=\dfrac{p}{(1-p)^2}$

因此有：

$\begin{aligned} f_{k,j} & = \sum_{i=0}^{\infty} p^i\times i\times(1-p)+\sum_{i=0}^{\infty} p^i\times(1-p)\times(j+k) \\ & = \dfrac{p}{(1-p)^2}\times(1-p)+\dfrac{1}{1-p}\times(1-p)\times(j+k) \\ & = \dfrac{p}{1-p}+j+k \\ \end{aligned}$

因此对于每一种不同 $j$，都乘上其对应期望计算即可。边界问题就这样解决了，配合前面的转移方程，就可以 $\operatorname{O}(k^2)$ 解决。

引理证明

$\sum_{i=0}^{\infty} p^i=\dfrac{1}{1-p}$

证明：

不难发现这是一个等比数列求和，我们记 $S=\sum_{i=0}^{\infty} p^i$，则 $S\times p=\sum_{i=1}^{\infty} p^i$，此时有：

$S\times p-S=\sum_{i=1}^{\infty} p^i-\sum_{i=0}^{\infty} p^i=-1$

又因为 $S\times p-S=S\times(p-1)$，所以 $S\times(p-1)=-1$，得到 $S=\dfrac{1}{1-p}$。证毕。

$\sum_{i=0}^{\infty} p^i\times i=\dfrac{p}{(1-p)^2}$

证明：

不难得到，原式可以转化为：$\sum_{i=1}^{\infty} p^i+\sum_{i=2}^{\infty} p^i+\sum_{i=3}^{\infty} p^i+\cdots+\sum_{i=\infty}^{\infty} p^i$

其中每一个 sigma 都是一个等比数列求和。我们用通法。设 $S=\sum_{i=a}^{\infty} p^i$，则 $S\times p=\sum_{i=a+1}^{\infty} p^i$，有 $S\times p-S=\sum_{i=a+1}^{\infty} p^i-\sum_{i=a}^{\infty} p^i=-p^a$。所以 $S\times(p-1)=-p^a$。

所以有 $S=\sum_{i=a}^{\infty} p^i=\dfrac{p^a}{1-p}$。到这里其实都是和前一个证明同样的方法。

然后将 $a\in\{1,2,3...,\infty\}$ 带进去，原式转化为：

$\dfrac{p+p^2+p^3+\cdots+p^{\infty}}{1-p}$

上面又是一个等比数列求和的式子。也就是 $\sum_{i=1}^{\infty} p^i$，接着套公式得到：

$\dfrac{p}{(1-p)^2}$

证毕。