概率与数学期望

daitouzero

·

2023-08-16 17:33:25

·

算法·理论

我是真的理解不来这些玩意

期望

对于一组离散型随机变量，出现其中某一变量的概率乘以这一变量值，再求和，就是数学期望，即 E=\sum p_{i}v_{i}

其实就是个类似平均数的玩意

期望有非常好的性质，如下

E(X+Y)=E(X)+E(Y)

E(aX+b)=aE(X)+b

这给了我们乱搞提供了数学基础

应用

算期望最直接的方法莫过于把所有情况的概率全部算出来，但是大部分情况下这都是不可能的——你要是算丢骰子几次能出 6 的期望，你还能算出所有丢出 6 的方案不成？

你要是说你给我整个无限序列求和那全当我没说，我甘拜下风

大部分情况下我们都是根据期望的线性性来 DP ，即 E(X+\Delta x)=E(X)+E(\Delta x)

一般问题在于怎么求这个 E(\Delta x)

SP1026 FAVDICE - Favorite Dice

问一个 n 面的骰子几次才能丢出所有面的期望

这题有两个想法，先说逆推的

dp[i] 表示的是已经丢出了 i 个面，丢出其他面要的期望次数

因为在已经丢出了 i 面的情况下，再丢一次总不能让出现过的面的种类减少吧

又一次最多只能丢出一面新的，固这玩意只会和 dp[i+1] 扯上关系

则有 dp_{i}=\frac{i}{n}dp_{i}+\frac{n-i}{n}dp_{i+1}+1

又因为我们开始只知道 dp[n]，目标是 dp[0] ，所以我们化一下，得到 dp_{i}=dp_{i+1}+\frac{n}{n-i}

以 dp[n]=0 为起点，逆推即可

第二个想法是根据应用里面那个式子来，我们考虑怎么求 E(\Delta x)

我们要求的这个增量就是在已经丢出 i 种面的情况下再丢出一种新面的期望次数

丢一次丢出新面的概率是 \frac{n-i}{n} ，根据 E=\sum p_{i}v_{i}

这个 E(\Delta x)=\frac{n}{n-i}\times 1+\frac{n}{i}\times 0=\frac{n}{n-i}

累加即可

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

为什么第 n 道题会涂到第 1 道题上啊喂

一样的，我们考虑怎么搞这个 E(\Delta x)

然后发现有点懵逼，不妨分类讨论一下试试看

当 a_{i}=a_{i+1} 时，显然两道题蒙对的几率没区别，期望就是 \frac{1}{a_{i+1}}

当 a_{i}

当 a_{i}>a_{i+1} 时，因为题 i+1 答案在 a_{i} 范围内的概率是 \frac{a_{i+1}}{a_{i}} ，故蒙对的概率是 \frac{a_{i+1}}{a_{i}}\times \frac{1}{a_{i+1}}

发现了！概率就是 \frac{1}{\max(a_{i},a_{i+1})}

那么 E(\Delta x)=\frac{1}{\max(a_{i},a_{i+1})}\times 1+(1-\frac{1}{\max(a_{i},a_{i+1})})\times 0=\frac{1}{\max(a_{i},a_{i+1})}

问题解决！

P1365 WJMZBMR打osu! / Easy

一样的，我们考虑计算每新加一个字符对现有期望的增量

加入的字符有三种可能 x ， o 和 ? ，最简单的就是 x ，因为它半毛钱贡献都没有

对于 o 和 ? 问题就有点麻烦了，因为贡献是个平方，所以我们必须得维护一个 len 表示期望的连续 o 长度

如果是一个 o ，那显然增加量是 (len+1)^2-len^2 ，因为贡献里面已经有了一个 len^2 ，为了避免重算，故减去

如果是一个 x ，因为这玩意的概率是相等的，所以期望的 len 就有一半概率加一，一半概率归零，故变为 \frac{len+1}{x}

这样题目也解决了

P1654 OSU!

刚刚看过了二次，这来个三次，艹

这题就等同于上一题全是 ? ，我们来搞这个 E(\Delta x)

根据 (x+1)^3=x^3+3x^2+3x+1，必须要维护二次项和一次项

假设我们新加入字符是 1 的概率为 p ，那么每一项归零的概率就是 1-p ,则一次项的期望就变成 (x+1)\times p+(1-p)\times 0

二次项的期望就是 (x^2+(2\times x+1))\times p+(1-p)\times 0

三次项的期望就是 (x^3+(3\times x^2+3\times x+1))\times p+(1-p)\times 0

直接每一步都用这三个式子套即可，不过注意更新的先后次序！

算期望很重要的一点就是不要瞻前顾后，老是想着之前要是断了怎么办，你要相信期望的线性性

更具体一些来说，上面这三个式子的第一项就是已有的值，不论前面是什么样，后面的新加的项都与这已有的值无关，两个之间没有关系，所以不会错

这种操作还可以上升到四次乃至 k 次，可以使用二项式定理来写，复杂度是 O(nk^2) 的

CF280C Game on Tree

序列上的做了不少，不如来个树

看见这玩意，人有点蒙圈，刚开始还天真的以为就是个简单的自底向上 DP，对每个节点统计儿子被删完的期望即可

但是关键在于它删的不一定从底开始啊，他可以直接把节点 1 删了，一次就删完了！

一次删除操作涉及多个节点，期望的性质明显不允许我们这么干

想到这，我们发现这删几次，或者说，一个节点能活多久，取决于比他祖先什么时候被删

不妨这么想，假设随机一个排列，我们从左往右依次删除节点如果它已经被删了就跳过

那么一个节点被删的充要条件就是比他浅的且是它祖先的节点没有一个在它前面

这个祖先节点的个数就是他的深度减一，所以它被删的概率是 \frac{1}{dep_{s}+1}，因为一个点肯定只能删一次啊，所以这个点被删的数量的的期望就是 \frac{1}{dep_{s}+1}（这话有点奇怪而且绕口，但咱也无能为力）

我们统计期望的意义也可以换一下，换成是 把树删要删几个节点，或者说 期望有多少节点被删

所以答案就是 \sum \frac{1}{dep_{s}+1}

P4550 收集邮票

看起来不是啥难题，实则暗藏玄机，每次抽取代价都会加一的条件简直坑爹

但不要怕，先想一下代价的式子应该长什么样

假设已经抽了 x 次，那么代价就是 \sum_{i=1}^{x}i=\frac{(x^2+x)}{2}

那现在就是求上面这个式子的期望，之前三次都会做出来了，这个相比也不难

分别维护一次项和二次项，一次项就是 SP1026，也就是第一道题，设一次项的数组是 a

二次项则有 f_{i}=\frac{i}{n}(f_{i}+2\times a_{i}+1)+\frac{n-i}{n} \times(f_{i+1}+2\times a_{i+1}+1)

化一下得 f_{i}=\frac{i}{n-i}(2\times a_{i}+1)+f_{i+1}+2\times a_{i+1}+1

倒推即可