20240710概率期望

概率

基础知识不写了，反正应该知道的都知道
但是有几个跟容斥有关的不知道，我要记录下
1.互斥事件可加性：对于n个互斥的事件\(P(A_1\cup ...\cup A_n)=\sum_{i=1}^{n}A_i\)
2.独立事件可乘性：对于n个对立的事件\(P(A_1\cap ...\cap A_n)=\prod_{i=1}^{n}A_i\)
3.n重伯努利实验：一次实验中某个事件发生的概率是P，那么重复n次独立事件中这个事件恰好发生k次的概率是\(P_{n}(k)=C_{n}^{k}\times p^{k}\times (1-p)^{n-k}\)
4.全概率公式：
如果\(B_1...B_n\)满足：
I.两两互斥
II.\(B_1\cup ...\cup B_n=\Omega\)
那么我们称\(B_1...B_n\)是样本空间\(\Omega\)的一个划分
公式就是：
设称\(B_1...B_n\)是样本空间\(\Omega\)的一个划分，A为任意事件，那么有：
\(P(A)=\sum_{i=1}^{\infty}P(B_i)\times P(A|B_i)\)
5.贝叶斯公式：
是建立在条件概率的基础上寻找事件发生的原因，设\(B_1...B_n\)是样本空间\(\Omega\)的一个划分，那么对任意事件A(\(P(A)>0\))，有：
\(P(B_i|A)=\frac{P(B_i)\times P(A|B_i)}{\sum_{j=1}^{n}P(B_i)\times P(A|B_i)}\)

期望

就是达到能做某一件事情的结果的期望
一般的计算公式是每次可能结果的概率乘以其结果的总和
\(E(X)=\sum_{i}x_i\times p_i\)

小性质

1.设X是随机变量，C是常数，那么\(E(CX)=C\times E(X)\)
2.设X，Y是随机变量，有\(E(X+Y)=E(X)+E(Y)\)
3.设X,Y是相互独立的随机变量，有\(E(XY)=E(X)\times E(Y)\)
4.设C为常数，有\(E(C)=C\)
证明很简单，就不证了。
5.全期望公式：
\(E(Y)=E(E(Y|X))=\sum_{i}P(X=x_i)E(Y|X=x_i)\)
1.推式子.
这个方法一般是用到了等比数列求和，极限等思想来解决问题。
2.递推或动态规划.
这是求解概率，期望问题的最常见的套路。其重要的是确定好思考的方向，不要将每个状态独立起来，而考虑对整体的影响。不然对于一些东西，求解并不方便。更要考虑优化动态规划，来达到更优的复杂度。
3.迭代.
动态规划要求问题无后效性， 而如果问题有不可避免的后效性， 动态规划就无能为力了。 这时我们可以采用迭代的方法来进行计算。在题目中没有出现极大或极小的概率且收敛较快时，可以使用这个方法，对于一些题目可以做到较优秀的复杂度。对于可能出现无限（也就是环）情况的，迭代至达到所求解的精度为止。此外， 迭代法也未必是要解决有后效性的问题， 只要问题有收敛性， 迭代都可以起到一定的作用。
4.高斯消元.
对于出现无限（环）的情况时，且精度要求较高，可以考虑列出期望-概率系统（概率—期望系统是一个带权的有向图，可以存在环），运用高斯消元来求解。但是对于环之间满足一个偏序时，可以用等比数列求和来求解，得到更优秀的复杂度。
问题分析:
对于一般的有限状态的问题，可以通过一般的递推，动态规划来求解。如果单纯的动态规划复杂度太高，且收敛较快，可以尝试使用迭代+动态规划来求解。
对于出现环的题目，尝试对问题建图，运用高斯消元来求解。
当然，如果概率比较难求解时，不妨用期望来间接求解。
\(P(x)=\frac{E(x)}{E(all)}\)
对于期望DP一般是逆推，记忆化搜索的写法可以很清楚的明白为什么。而概率DP一般是正着推。