期望 | Creator's World

期望

2021-04-23 12 min read # 期望 # 学习笔记

OI 中常见的期望知识。

一、什么是期望

在 OI 中我们常指的期望是达到结果的期望，简单来说就是 每次可能结果的概率乘以其结果的总和。

一个离散性随机变量 $X$ 的数学期望是每个取值乘以该取值对应概率的总和，记为 $E(X)$ 。

E(X) = \sum_{\alpha\in I(X)} \alpha \cdot P(X=\alpha) = \sum_{\omega\in S}X(\omega)P(\omega)

其中 $I(X)$ 表示随机变量 $X$ 的值域， $S$ 表示 $X$ 所在概率空间的样本集合。

二、性质

设 $X$ 是随机变量， $C$ 是常数，则 $E(CX) = C \times E(X)$ 。

证明：设 $X$ 的多个随机变量为

C_{a_1},C_{a_2},C_{a_1},\ldots,C_{a_n}

对应的出现概率为

p_1,p_2,p_3,\ldots,p_n

那么对应的求期望的式子

E(CX) = C\sum_{i=1}^{n}(a_i\times p_i)

将 $C$ 提出，因为

E(X) = \sum_{i=1}^n(a_i\times p_i)

所以

E(CX) = C \times E(X)

设 $X,Y$ 是任意两个随机变量，则有 $E(X+Y) = E(X) + E(Y)$ 。
设 $X,Y$ 是任意两个相对独立的随机变量，则有 $E(XY) = E(X) \times E(Y)$ 。
设 $C$ 为常数，则 $E(C) = C$ 。

三、赠券收集问题

SP1026 FAVDICE - Favorite Dice

设已经有了 $i-1$ 个不同的面，掷一次新的面的概率为 $\frac{n-i+1}{n}$ ，而期望是概率的倒数，即 $\frac{n}{n-i+1}$ 。

其实挺好理解的，相当于期望选 $n$ 个球才选到 $1$ 个红球，那么选到红球的概率为 $\frac{1}{n}$ 。

而根据期望的性质：设 $X,Y$ 是任意两个随机变量，则有 $E(X+Y) = E(X) + E(Y)$ ，使得每一面都被掷到的期望就是 $\sum_{i=1}^n \frac{n}{n-i+1} = \sum_{i=1}^n \frac{n}{i}$ 。

UVA10288 优惠券 Coupons

显然还是一样的，有公式 $\sum_{i=1}^n \frac{n}{i} = n\times \sum_{i=1}^n \frac{1}{i}$ ，而后面的东西似乎叫调和级数。本题最烦的就是要输出带分数，因此我们可以预处理调和级数。

至于如何预处理，设计算到第 $i$ 个数， $a,b$ 是 $i$ 前面分数的前缀和的分子和分母，则有 $\frac{a}{b}+\frac{1}{i}=\frac{a \times i + b}{b \times i}$ ，然后转移即可。

P1291 [SHOI2002]百事世界杯之旅

上题的双倍经验。

四、高次期望

其实就是一些在一次期望基础上增加维度的题目，掌握了一次转二次的方法即可（其实就是初中数学知识）。

设 $E(X_i)$ 为在第 $i$ 个位置得分的期望值，再考虑 $E(X_{i+1})$ 和 $E(X_i)$ 的关系。

设 $i$ 为值产生连续一串长度为 $l$ 的概率为 $p_l$ ，在 $i+1$ 位置是 $1$ 的概率为 $P$ ，那么对于每一个单独的 $l$ 它都有 $P$ 的概率对分数产生 $3\times l^2 + 3\times l + 1$ 的额外贡献。

考虑所有的 $l$ ，得式子

E(X_{i+1}) = E(X_{i}) + P \cdot \sum_{l=0}^{i} p_l (3\cdot l^2 + 3\cdot l + 1)

根据期望的式子发现

\sum_{l=0}^ip_ll^2=E(l^2)

\sum_{l=0}^ip_ll=E(l)

于是式子转化为

E(X_{i+1})=E(X_i) + P \cdot (3\cdot E(l_i^2) + 3\cdot E(l_i) + 1)

这样我们就把一个高次的期望转化为低一级的期望，而 $E(l_{i+1})$ 和 $E(l_{i+1}^2)$ 可以通过类似的方法求出。

E(l_{i+1}) = P\cdot (E(l_i) + \sum_{l=0}^ip_l) = P\cdot (E(l_i) + 1)

E(l_{i+1}^2)=P\cdot (E(l_i^2)+2\cdot E(l_i) + 1)

事实上我们通过思考 $E(i+1)$ 和 $E(i)$ 的关系得出 $E(i+1)$ 的关系式后，可以通过

(x+1)^2=x^2 + 2\cdot x + 1

得出二次期望，类似的得出三次期望，以此类推。

CF235B Let's Play Osu!

与上题类似，只不过是求二次期望，那么只要二次期望的式子变一下就好了。

P1365 WJMZBMR打osu! / Easy

上题的双倍经验。

五、期望 dp

其实大多数期望都可以用 dp 的形式表示，只不过这类更关键的还是 dp，感觉就是 dp 的基础上加了期望。

P1850 [NOIP2016 提高组] 换教室

首先显然有状态 $f_{i,j}$ 表示前 $i$ 个时间段换了 $j$ 次课的最小期望值，但是我们发现无法转移，由于有换教室的操作，所以我们不知道当前状态从哪里转移过来，而常见的处理方法就是多加一位数组。
我们设 $f_{i,j,0/1}$ 表示前 $i$ 个时间段换了 $j$ 次课且第 $i$ 个时间段换 $/$ 不换的最小期望值，这就很好转移了。

预处理时跑一遍最短路即可。注意！floyd 中的中间点要放到最外层枚举！

P2473 [SCOI2008] 奖励关

看到集合、 $n\leq 15$ 就可以发现很明显是个状压 dp，很显然有状态 $f_{i,s}$ 表示前 $i$ 关状态为 $s$ 的期望得分。但这样是有错误的，因为可能第 $i$ 轮不能到达状态 $s$ 。

正推不行就逆推。设 $f_{i,s}$ 表示第 $1$ 轮到第 $i-1$ 轮取的情况为 $s$ ，从 $i$ 到 $k$ 的期望得分。那么只要枚举就行了。

上面求的东西覆盖了所有 $n$ 个宝物的情况，所以每次计算完后要除以 $n$ 。

六、随机游走

一般是在图上，随机选择一条边向前，问期望行走步数。

P6835 [Cnoi2020]线形生物

对于这种求期望步数的题目，设 $E_{x\rightarrow x+1}$ 表示从 $x$ 到 $x+1$ 的期望步数，则答案为 $\sum_{i=1}^n E_{i\rightarrow i+1}$ 。

那么推一波式子（ $deg_x$ 表示 $x$ 的返祖边边数， $e$ 表示返祖边组成的集合）

E_{x\rightarrow x+1} = \frac{1}{deg_x + 1} + \frac{1}{deg_x+1}\sum_{(x,y)\in e} E_{y \rightarrow x+1} + 1

而 $E_{y \rightarrow x + 1}$ 又可以表示成 $\sum_{i=y}^x E_{i\rightarrow i+1}$ ，那么式子可以转化为

E_{x\rightarrow x+1} =1 + \frac{1}{deg_x+1}\sum_{(x,y)\in e} \sum_{i=y}^x E_{i\rightarrow i+1}

设 $f_x = E_{x\rightarrow x+1}$ ，显然可以用前缀和优化右边那一坨，设 $sum_x=\sum_{i=0}^x f_i$ ，式子化为

f_x =1 + \frac{1}{deg_x+1}\sum_{(x,y)\in e} sum_x-sum_{y-1}

发现左右两边都有 $f_x$ ，不便于转移，将 $f_x$ 都移到左边

f_x=deg_x+1+\sum_{(x,y)\in e} sum_{x-1}-sum_{y-1}

然后就可以愉快地转移啦！

对了还有，用 long long 的时候不要省那点空间和时间！想这种要取模的，中间极有可能爆 int，一定要开 long long！

一道不用期望的期望题。设 $sum$ 为所有的路径长度， $num$ 为所有的路径条数，那么答案就是 $\frac{sum}{num}$ ，那么只要记搜求出所有点能走的路径长度 $f_i$ ，所有点能走的路径条数 $g_i$ 即可。

转移

f_u = \sum_{v \ is \ u's \ son } f_v+g_v

g_u = 1 + \sum_{v \ is \ u's \ son } g_v

七、杂题

P1297 [国家集训队]单选错位

挺简单的一道期望题，但自己想都不想就去看题解，明明自己可以做出来。以后不管什么题目至少想 $15\sim 30$ 分钟。

下一篇

树形 dp