概率与期望
定义
期望：对于一个离散随机变量\(X\)，自变量的取值范围为\(\{x_1,x_2,x_3,... \,,x_n\}\)，\(P(x_i)\)为\(X=x_i\)的概率。其期望被定义为：
\[E(X)=\sum^n_{i=1}x_iP(x_i) \]简单理解就是加权平均。
公式
贝叶斯公式：
全概率公式：
应用
1、有 \(k\) 只小鸟，每只都只能活一天，但是每只都可以生出一些新的小鸟，生出 \(i\) 个小鸟的概率是 \(P_i\)，最多生出\(n\)只小鸟。问 \(m\) 天所有的小鸟都死亡的概率是多少。
先考虑一只小鸟：设\(f_i\)为第\(i\)天小鸟全部死亡的概率。
对于一只小鸟：\(f_i=\sum^n_{i=0}P_i*f^i_{i-1}\)
解释：一只小鸟，可能第一天就嗝屁了，概率为\(P_0\)，也有\(P_k\)的概率生了\(k\)只鸟，这\(k\)只鸟会经历和它们父亲相同的命运，但是它们只需要挺过\(i-1\)天就不会被计进\(f_i\)中，故为\(f_{i-1}\)，又因为\(k\)只鸟相互独立，故全部死亡概率为\(f^k_{i-1}\)
则答案为\(f_m^k\)
2、假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于多少？
考虑用期望计算
对于红球，\(E(X)=1\)，因为所有抽完的人都有且仅有1个红球
对于蓝球，有\(E(X)=\frac{1}{2}*0+\frac{1}{2}(1+E(X))\)，解得\(E(X)=1\)
解释：一次抽奖，抽到了红球结束，抽到蓝球继续抽，此时，注意到“继续抽”这个行动和原行动等价，则期望相同，带入求即可
总结
观察可得，两道题通过分类讨论找到全部情况，从而求出答案，这是概率与期望的常见做法
上面两题给我们启发：对于有限数量状况的事件（\(X\)取值有限），列举全部情况，找出等价的子问题，进行递推；对于无限的情况，找出的等价子问题相当于原问题（类比生成函数的推导），通过解方程得到答案
期望DP
期望DP中，常用逆推的方法求解，具体理解见例题
模型
基于DP的转移，可以发现几种模型
首先我们知道，DP的转移构成DAG，而在期望DP设计状态方程时，常有环出现，这是根据DP状态定义而出现的
最大环为自环
移项，做DAG DP即可
最大环不为自环
一般换定义、解方程（高斯消元）
P4316 绿豆蛙的归宿
正推
按顺势思路，设\(f[i]\)为从1到\(i\)的期望路径长
递推方程：
\[f[x]=\sum^V_{i \to x}\frac{1}{d_i}(f[i]+p[i]*dis_{i \to x}) \]其中\(p[i]\)为从1到\(i\)的概率
于是引出一个问题：为什么\(dis_{i \to x}\)要乘\(p[i]\)呢？
我们回归定义：\(E(X)=\sum^n_{i=1}x_iP(x_i)\)
根据定义，我们要求的是每条路径的加权平均值，即该路径出现的概率乘路径长
由于路径不好做，我们拆开成若干条边，对边进行统计
当我们将边\(i \to x\)的贡献加入时，必须想到，边是路径的子集，因此概率也要按占有该边的路径计算
逆推
逆推思路没有正推直观
设\(f[i]\)为从\(i\)到\(n\)的期望路径长
递推方程：
\[f[x]=\sum^V_{x \to i}\frac{1}{d_x}(f[i]+dis_{x \to i}) \]于是又引出一个问题：为什么这时候又不用乘了呢？
因为概率是正确的
仔细想想逆推回去，\(dis_{x \to i}\)会发生什么
会乘上各种\(\frac{1}{d_i}\)，然后各种累加
然后就会发现，它乘上的概率刚好就是路径的概率，即前面的\(p[i]\)
感觉不出来可以手画一下
p.s.概率DP常用正推，期望DP常用逆推
P4562 [JXOI2018] 游戏
这是一道可以用期望做的统计题
用埃筛求出所有不为别的数的倍数的数——该数集取完才能结束（注意这里时间复杂度是\(O(n\log\log n)\)）
统计法枚举长度+排列组合即可
期望法：（待办）
P3750 [六省联考 2017] 分手是祝愿
先考虑\(k=n\)部分，即求一个贪心策略，容易发现最大的数只能被自己更新，从大到小贪心做即可，时间复杂度\(O(n\sqrt n)\)或\(O(n\log n)\)
再考虑满分做法，由于上面贪心策略中，每个数都不可替代，所以必须取到上面的全部数才可结束，而取不到该数集又会使必须数增加\(1\)（因为要按回来），考虑枚举取数个数进行DP
设\(f[i]\)为必须数还有\(i\)个数没取，想要达到结束态的期望操作数
易得方程\(\displaystyle f[i]=\frac i n*f[i-1]+\frac {n-i} n*f[i+1]+1\)
发现该方程出现大于自环的环，而高斯消元又不可承受，考虑如何处理
模拟高斯消元
由于矩阵中每一行非零元只有\(3\)个，考虑直接模拟消元过程
解方程，推式子
考虑一组这样的方程：
\[\begin{cases}\displaystyle f[i]=f[i-1]+1\hspace{3.6cm},i=n\\\displaystyle f[i]=\frac i n*f[i-1]+\frac {n-i} n*f[i+1]+1\ \ ,\text{otherwise} \end{cases} \]对其尝试回代，得\(\displaystyle f[n-1]=f[n-2]+\frac{n+1}{n-1},...\)
回代几组发现，这几个式子都满足\(f[i]=f[i-1]+C\)，且几个式子的\(C\)存在递推关系，为\(\displaystyle g[i]=\frac{n-i} i*g[i+1]+\frac n i\)
最后求\(f[]\)即可，时间复杂度\(O(n\log n)\)（逆元）
换定义
设\(f[i]\)为从\(i\)转移至\(i-1\)的期望操作次数，则
相当于把贡献拆成了\(n\)份，之后再统计起来
\(\displaystyle f[i]=\frac i n+\frac{n-i}n*(f[i+1]+f[i]+1)\)
第二部分是没选到数集，必须数增加\(1\)，需要\(f[i+1]\)步转回来，再\(f[i]\)走到下一步
最终贡献为\(\displaystyle \sum_{i=k+1}^{n}+k\)
总结
理解之后一身轻，关键在于找到状态，列方程就简单了
标签：概率,期望,小鸟,frac,动态,规划,displaystyle,DP From： https://www.cnblogs.com/zhone-lb/p/18522185