概率期望
|
3.6k 字
|
15 分钟

概率

  • 离散型随机变量：只有有限种可能值的随机变量

  • 连续型随机变量：随机变量 x 的分布函数可以表示成一个非负可积函数 f(x) 的积分

  • 对于同一样本空间下的互斥事件，P(A+B)=P(A)+P(B)P(A+B) = P(A)+P(B)

  • 推论：对于全部的基本事件来说∑P(ei)=1\sum P(e_i) = 1

  • 条件概率：记P(B∣A)P(B|A)表示在A事件下发生的前提下，B事件发生的概率，则P(B∣A)=P(AB)P(A)P(B|A) = \dfrac{P(AB)}{P(A)}P(AB)P(AB)指的是事件A和B同时发生的概率

  • 全概率公式：若事件A1,A2...AnA_1,A_2...A_n构成一个完备的事件且都有正概率，即∀i,j,Ai∩Aj=∅\forall i,j,A_i\cap A_j = \varnothing且∑i=1nAi=1\sum_{i=1}^{n}A_i = 1，有P(B)=∑i=1nP(Ai)P(B∣Ai)P(B) = \sum_{i=1}^{n}P(A_i)P(B|A_i)。

  • 贝叶斯定理：P(Bi∣A)=P(Bi)P(A∣Bi)∑j=1nP(Bj)P(A∣Bj)\huge{P(B_i|A) = \dfrac{P(B_i)P(A|B_i)}{\sum_{j=1}^{n}P(B_j)P(A|B_j)}}

  • 期望：设离散型随机变量x的分布为：P(X=xi)=pi(i=1,2,3...,n))P(X=x_i)=p_i(i=1,2,3...,n))，那么X的数学期望就是∑i=1nxipi\sum_{i=1}^{n}x_ip_i，期望具有线性性，E(aX+bY+cZ)=aE(X)+bE(Y)+cE(Z)E(aX+bY+cZ)=aE(X)+bE(Y)+cE(Z)

  • 对于两个独立的随机变量X，Y来说，E(XY)=E(X)+E(Y)E(XY) = E(X)+E(Y)

我们考虑一下什么时候用概率dp什么时候用期望dp

对于一个题来说，我们只需要简单的概率操作，但是带权的话不是很好求权值。如果说状态是可以和概率进行绑定的，前置状态会不会有什么对之后的影响，就有很多是可以用概率DP进行求解的，如果 一个题目他的状态是和概率绑定的，但是这个概率并不一定在这个位置产生贡献的话，也是一般用的是期望dp。

(听课时知道的一个小trick)：如果说对于一个满二叉树来说，我们在求这棵树上面两个点的lca时：由于我们可以在这棵树上面发现，要么是从根节点的左儿子走，要么是右儿子走，那么我们就可以吧这个数字表示成一个01序列，那么我们会发现，两个数字的01序列最前边一样的位置就是lca（很妙对吧，

倒推法是在进行期望dp的时候的一个很重要的优化方法，因为起点固定但是重点并不一定是固定的，那么在进行倒推的时候我们就可以直接求出来起点的贡献，然后就可以直接输出了就不需要求和了（也不需要求和的时候的一堆判断了

例题：

竞赛

给定n，总共有2n2^n个人，刚开始的时候站成一排，相邻两个人进行对决，给定每个人和其他所有人对决获胜的概率，求谁的获胜概率更大

我们考虑对每一个人进行求解

f[i][j]f[i][j]表示第i轮比赛，j获胜的概率，那么我们会发现，我们并不知道j在第i轮会和谁打，但是我们可以知道j在第i轮可能会和谁打，并且我们在dp的时候可以知道和谁打架的概率，就是那个人在第i轮胜出的概率

那么转移方程不就出来了吗：f[i][j]+=f[i−1][j]∗f[i−1][k]∗p[j][k]f[i][j] += f[i-1][j]*f[i-1][k]*p[j][k]然后就可以求出来f[i][j]f[i][j]了，然后对于每一个人来说比较一下就好了

奖励关

题目链接

这是一道状压概率题目

还是挺简单的对吧

我们设状态f[i][j]f[i][j]表示第i个物品下落的时候，吃的物品的种类数的状态是j的期望收益

然后转移就比较明显了吧，对于每一个物品的种类进行一次转移就可以了

（虽说这个题是个紫色但是思维难度并没有那么大对吧

P5104 红包发红包

我们会发现第一个人获得的钱的期望就是∫0wxw=w2\int_{0}^{w}\dfrac{x}{w} = \dfrac{w}{2}

后面的人获得的钱的期望值就是w2n\dfrac{w}{2^n}

然后快速幂就好了

P1850 [NOIP2016 提高组] 换教室

很经典的一道题

我们首先考虑，如果说我们这个位置换，还是不换

那么这个位置有两个选择，但是上一个位置同样也是两个选择

那么其实总共应该是四个选择对吧（对于每一个阶段来说

那么我们就可以dp一遍求值了嘛：设置f[i][0/1]f[i][0/1]表示这个位置换还是不换

但是如果说换的话就需要判断一下能不嫩换成了，所以要乘上概率

我们看到了n的数据范围，我们就可以先用floyd处理任意两点之间的最短路

就完事了

P3830 [SHOI2012]随机树

第一问好说，我们会发现，设f[x]f[x]表示在有x个叶子节点的时候叶子节点平均深度

那么我们会发现，只要是多展开了一个节点，深度就会增加f[x−1]+2f[x-1]+2

那么就可以推了：f[x]=f[x−1]∗(x−1)+f[x−1]+2xf[x] = \dfrac{f[x-1]*(x-1)+f[x-1]+2}{x}

但是另一问不好做哦：

我们考虑如果说这棵树上面有i个节点,深度为j的时候应该怎么办

那么我们会发现，深度为j的地方才会增加深度但是别的地方并不会

那么我们设f[i][j]f[i][j]表示有i个叶子节点，并且深度为j的概率

我们会发现，f[i][j]=∑k=1i−11i−1f[k][j−1]+f[i−k][j−1]−f[k][j−1]∗f[i−k][j−1]f[i][j] = \sum_{k=1}^{i-1} \dfrac{1}{i-1} f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1]，为什么会有后边的呢，是因为只要两边子树任何一个深度为j-1就可以转移了所以会有重复的情况发生，并且因为总共有i个叶子节点，所以并不知道会展开哪个，所以乘上了i-1分之一

答案就是∑i=1nf[n][i]\sum_{i=1}^{n}f[n][i]

P1654 OSU!

太难了……这就是概率期望嘛

首先我们知道一件事情就是三次方的期望并不等于期望的三次方，所以我们并不能单纯的求出来期望长度然后三次方

我们会发现(x+1)3−x3=3x2+3x+1(x+1)^3-x^3 = 3x^2+3x+1所以我们可以求出来平方和个位数的期望然后相加

期望贡献就是：f[i]=f[i−1]+(3∗(E((i−1)2)+E(i−1))+1)∗p[i]f[i] = f[i-1]+(3*(E((i-1)^2)+E(i-1))+1)*p[i]

但是事实上他可以写成这个式子,更加方便理解：

f[i]=(1−p[i])∗f[i−1]+(f[i−1]+3∗E((i−1)2)+3∗E(i−1)+1)∗p[i]f[i] = (1-p[i])*f[i-1]+(f[i-1]+3*E((i-1)^2)+3*E(i-1)+1)*p[i]

前半部分就是这一位并不是o的贡献，后面是这一位是o的贡献

P4550 收集邮票

f数组表示现在已经取到了i张邮票，要取完剩下的邮票的期望次数

我们先求出一个f数组：f[i]=f[i]∗in+n−in∗f[i+1]+1f[i] =f[i]*\dfrac{i}{n}+\dfrac{n-i}{n}*f[i+1]+1很好推对吧

但是还要求g数组哦：

我们会发现，现在取了一张邮票，其实就相当于吧后面的邮票所有都加了1块钱

所以：g[i]=in∗(f[i]+g[i]+1)+n−in∗(f[i+1]+g[i+1]+1)g[i] = \dfrac{i}{n}*(f[i]+g[i]+1)+\dfrac{n-i}{n}*(f[i+1]+g[i+1]+1)

这就很自然对不对，然后化简一下递推就好了

CF908D New Year and Arbitrary Arrangement

我们会发现，如果说前面的a的数量加上已经有的ab的数量大于等于k了，我们在后面加一个b就直接完事了对吧

我们设f[i][j]f[i][j]表示前面已经有了i个a，j个ab停止后的期望长度

那么我们转移的时候就可以很自然了

f[i][j]=i+j+cf[i][j] = i+j+c当i+j>=k的时候

f[i][j]=A∗f[i+1][j]+B∗f[i][i+j]f[i][j] = A*f[i+1][j]+B*f[i][i+j]（倒推嘛

判断一下就好

P2081 [NOI2012] 迷失游乐园

基环树dp（恶心死我了，为什么总有毒瘤出题人愿意出基环树

一道基环树的概率题目

我们还是要先考虑一下并不是基环树的情况

我们考虑一个点，他要不然是向上走要不然是向下走，那么我们就分情况被

假如说它向下走，那么 期望长度不就是子树向下走加上这条边的长度之和的平均嘛

然后我们考虑向上走，向上走，只要不是根节点，就一定会再次向下走（排除根节点只有一个子树的情况

那么我们会发现，我们就是向上找到第一个往下走的点呗

然后考虑基环树的情况

我们也就是枚举基环树上面的点为根嘛

枚举一遍求一下就好了，但是由于在基环树上面，所以度数要增加2滴

并且说，基环树在环上是可以顺时针逆时针随便走的

然后走到一个点之后把他的down算上就是期望长度之一

P5249 [LnOI2019]加特林轮盘赌

我们会发现一件事情：死了一个人之后人的总数会减少欸（废话

那么在减少一个人的时候，总数就会减少，（就可以转移

如果没有减少一个人的话，就相当于是这个人到了最后一位，也可以转移

我们设f[i][j]f[i][j]总共剩下i个人，现在第j个人存活的概率

f[i][j]=p∗f[i][j−1]+(1−p)∗f[i−1][j−1]f[i][j] = p*f[i][j-1]+(1-p)*f[i-1][j-1]

然后消元就好了（用所有概率相加等于1来消元

∑j=1np[i][j]=1\sum_{j=1}^{n}p[i][j] = 1

P2473 [SCOI2008] 奖励关

状压+概率期望（两个讨厌的东西拼在一起就变得更讨厌了

就记录一下当前的宝物种类已经吃了的状态状压进去，然后记录当前实在第几位

然后暴力转移就好了啊

P3750 [六省联考 2017] 分手是祝愿

我们先求出来最少需要多少次操作，那肯定是从大到小先判断一边

然后我们就假设一下f[i]表示现在最少还需要x次才可以（其实并不是最少，而是必须

那么我们会发现，随机选择出来一个按钮进行按的话，有可能按成对的，也有可能按成错的

那么我们的转移方程就会变成: f[i]=in+(n−i)n∗(f[i+1]+f[i]+1)f[i] = \dfrac{i}{n}+\dfrac{(n-i)}{n}*(f[i+1]+f[i]+1)

后面的东西是先错一次，然后再变成对的

那么就好说了，我们可以把f[i] 变成一个只与f[i+1]有关的式子

然后就可以递推了

注意不是一直递推到f[0]或者f[1]而是f[k]并且从cnt开始推哦

然后最后求一边和就好了

P3239 [HNOI2015]亚瑟王

这个题就求出来每一张卡被使用的概率，然后乘上权值

但是概率咋算（好难）（但是f[1]并不难算，1−(1−p[1])r1-(1-p[1])^r

令f[i][j]f[i][j]表示在前i张卡中出了j张卡的概率，那么我们有个性质：

如果说前i张卡出了j张卡，那么有r-j+1轮有可能第i张卡发动，那j轮这张卡根本没有机会发动

那么f[i][j]+=(1−(1−p[i])r−j+1)∗f[i−1][j−1]f[i][j] +=(1-(1-p[i])^{r-j+1})*f[i-1][j-1]

f[i][j]+=(1−(1−p[i])r−j)f[i−1][j]f[i][j]+=(1-(1-p[i])^{r-j})f[i-1][j]

那么这张卡用过的概率g[i]=f[i−1][j]∗(1−(1−p[i])r−j)g[i] = f[i-1][j]*(1-(1-p[i])^{r-j})

上面的式子就是说，前面i-1张用了j张的概率乘上这张用了的概率然后求和

（概率期望真**难啊

上一篇
下一篇