概率 dp、期望 dp

xujingyu · 2024-08-22 16:02:31 · 算法·理论

常用概念几何概型

为了简化概念，此处只涉及有限的样本空间和离散的事件。
基本事件：不可再分割，随机变量的某个取值，也叫样本点 𝜔 比如单次投掷出 5 即为基本事件
事件 𝐸：基本事件的某个集合体比如投掷结果为偶数
样本空间 Ω：所有的基本事件比如投掷一个骰子得到的所有可能结果构成样本空间
示性函数 𝐼_𝐴：如果得到的结果是事件 𝐴，则该值为 1，否则为 0。

概率

概率本质上就是从事件到一个实数值的函数，通常记作 𝑃。概率必须满⾜三个条件：

（非负性）对任意事件 𝐴 都有 𝑃(𝐴)\leq0；
（正规性）𝑃(Ω)=1；
（可加性）如果事件 𝐴_1,𝐴_2,\dots 两两互斥，那么 𝑃(ڂ𝐴_𝑖)=\sum𝑃(𝐴_𝑖)。
- 互斥事件：发生 𝐴 则不可能发生 𝐵，则称事件 𝐴 和 𝐵 互斥（今天是周四与今天是周五）；
- 对立事件：𝐴 和 𝐵 互斥，且要么 𝐴，要么 𝐵（今天是周五和今天不是周五）。

概率的解释

概率的解释到现在都是一个有争议的话题。学者分为两派：

频率学派：认为概率是相对频数的极限，是一种客观属性。这其实是⼤多数⼈一开始接触概率时的看法。这一说法适⽤于可以反复观测的事件，随着观测次数趋于⽆穷，事件发生的相对频数会越来越趋近于真正的概率。如掷骰子。
⻉叶斯学派：认为概率描述的是信⼼的程度，带有一些主观的成分。比如，可以说“明天下⾬的概率是 90\%”，但显然我们⽆法多次观测这一事件。这⾥的 90\% 代表我们对于“明天下⾬”这一事件的信⼼，将来如果我们得到的新的数据（比如云层的变化），我们可能会对这一信⼼进⾏修正。

独⽴事件与条件概率

独立：对于事件 𝐴 和 𝐵，如果 𝑃(𝐴𝐵)=𝑃(𝐴)𝑃(𝐵)，那么称 A 和 B 是独立的。（注：𝐴𝐵 表示 𝐴 和 𝐵 的交集，𝐴+𝐵 表示两者的并集）所谓独立，即一次实验中一事件的发生不会影响到另一事件发生的概率。例如一般连续两次掷骰子得到的点数结果是相互独立的。
条件概率：如果 𝑃(𝐵)>0，那么 𝐴 在 𝐵 下的条件概率为 P(𝐴|𝐵)=\dfrac{𝑃(𝐴𝐵)}{𝑃(𝐵)} 即，已知 B 发生，在此前提下 𝐴 发生的概率是多少。特别地，如果 A 与 𝐵 独立，那么 𝑃(𝐴|𝐵)=𝑃(𝐴)。如 B 是骰子投到偶数，A 是投到 2。根据公式就是 \dfrac{1}{3}。

全概率公式

全概率公式：如果样本空间可以被划分为两两互斥的若⼲部分 A_1,\dots,𝐴_𝑘，即 𝐴_1+𝐴_2+\dots+𝐴_𝑘=Ω，那么 𝑃(𝐵)=\sum\limits_{𝑖=1}^k𝑃(𝐵|𝐴_𝑖)𝑃(𝐴_𝑖)。

全概率公式⽤于将不好算的事件拆分成若⼲个⼩的事件，分别计算。

⻉叶斯公式

公式

⻉叶斯公式：对于事件 𝐴 和 𝐵，如果 𝑃(𝐴)>0 且 𝑃(𝐵)>0，那么 P(𝐴|𝐵)=\dfrac{𝑃(𝐵|𝐴)𝑃(𝐴)}{𝑃(𝐵)}。

通常我们会有样本空间的一个划分 𝐴_1,\dots,𝐴_𝑘，结合全概率公式，对于任意 1\le 𝑖\le 𝑘 有：

P(𝐴_𝑖|𝐵)=\dfrac{𝑃(𝐵|𝐴_𝑖)𝑃(𝐴𝑖)}{P(B)}\\ P(𝐴_𝑖|𝐵)=\dfrac{𝑃(𝐵|𝐴_𝑖)𝑃(𝐴𝑖)}{\sum\limits_{j=1}^kP(B|A_j)P(A_j)}

⻉叶斯公式的解释

⻉叶斯公式其实是条件概率公式的直接推论。它描述的是这样的事实：

⻉叶斯公式的应用：垃圾邮件识别

我们可以利⽤⻉叶斯公式做一个简单的⼩程序来识别垃圾邮件。

所有邮件分为两类：𝐴_1 代表垃圾邮件，𝐴_2 代表非垃圾邮件。根据经验，𝑃(𝐴_1)=0.7，𝑃(𝐴_2)=0.3。（先验概率）

令 𝐵 表示邮件包含“免费”这一关键词，由历史邮件得知，P(𝐵|𝐴_1)=0.9，𝑃(𝐵|𝐴_2)=0.01（似然函数，注意：它们之和无意义且并不一定等于 1）。

新收到一封邮件，其中包含了“免费”词汇，它是垃圾邮件的概率是：

𝑃(𝐴_1|𝐵)=\dfrac{0.9\times0.7}{(0.9\times0.7)+(0.01\times0.3)}≈0.995

三门问题

有三扇⻔，其中一扇⻔背后有奖⾦，剩下两扇背后什么也没有。你选择了其中一扇⻔，此时主持⼈从剩下的两扇⻔中选择了一扇打开，后⾯什么也没有。此刻你是否应当更改选择另一扇没开的⻔？

直觉似乎是改不改⽆所谓，但我们可以⽤⻉叶斯的理论计算一下。

不妨设你选择的⻔是第 1 扇，主持⼈打开的是第 3 扇。设每扇⻔后⾯有奖⾦的事件为 𝐴_𝑖，那么先验概率为 𝑃(𝐴_𝑖)=\dfrac{1}{3}，我们想知道的是 𝑃(𝐴_1|\overline{𝐴_3}) 是多少。根据⻉叶斯公式有：

𝑃(𝐴_1|\overline{𝐴_3})=\dfrac{𝑃(\overline{𝐴_3}|A_1)P(A_1)}{𝑃(\overline{𝐴_3}|A_1)P(A_1)+𝑃(\overline{𝐴_3}|A_2)P(A_2)+𝑃(\overline{𝐴_3}|A_3)P(A_3)}

其中：

如果奖⾦在第 1 扇⻔后⾯，主持⼈可以打开第 2 或者第 3 扇⻔，概率相同。因此 𝑃(\overline{𝐴_3}|A_1)=\dfrac{1}{2}；
如果奖⾦在第 2 扇⻔后⾯，主持⼈只能打开第 3 扇⻔。因此 𝑃(\overline{𝐴_3}|A_2)=1；
如果奖⾦在第 3 扇⻔后⾯，显然 𝑃(\overline{𝐴_3}|A_3)=0。

带入可得 𝑃(𝐴_1|\overline{𝐴_3})=\dfrac{1}{3}，因此更换选择后中奖概率更高，𝑃(𝐴_2|\overline{𝐴_3})=\dfrac{2}{3}。

更直观的认识：

随机变量

表示将样本点映射到实数域的函数 𝑋:Ω→𝑅。

例如，投掷一个骰子，得到的结果有 1,2,3,4,5,6。

最简单的实值函数即为结果本身，即投掷结果。

如果考虑投掷两个骰子，那么这个实值函数可以为两者之和和两者中的较⼤值。

例如记随机变量 𝑋 为两个投掷结果之和，则 𝑋 的可能取值为 2,3,\dots,12。

记随机变量 𝑌 为两个投掷结果中的较⼤值，则 𝑋 的可能取值为 1,2,3,4,5,6。

期望

定义

随机变量在概率意义下的平均值 E[𝑋]=\sum\limits_{𝜔∈Ω}𝑋(𝜔)𝑃(𝜔)。

举个例子，假设抽奖得到一⼆三等奖和谢谢惠顾的事件分别为 A_1,\dots,𝐴_4，其概率分别为 0.01,0.02,0.07,0.9。那么设随机变量 𝑋 代表抽奖得到的奖⾦，𝑋(𝐴_1)=1000,𝑋(𝐴_2)=500,𝑋(𝐴_3)= 100,𝑋(𝐴_4)=0，其期望为 𝐸[𝑋]=1000\times0.01+500\times0.02+100\times0.07+0\times0.9=27。

这意味着抽奖券⾄少得卖 27 元。

期望的性质

线性：对于任意随机变量 𝑋 和 𝑌，满⾜ E[𝛼𝑋 +𝛽𝑌]=𝛼𝐸[𝑋]+𝛽𝐸[𝑌]。

期望的线性性是始终成立的，⽆论两随机变量是否独立。

做题最常⽤的性质。

OI 中解概率题的常见套路

题目是一个很直接的数学题，直接使⽤数学方法；
递推，动态规划（状态之间满⾜拓扑序）；
高斯消元（状态之间不满⾜拓扑序）。

矩形粉刷

有一块 𝑁\times𝑀 的矩形⽹格要进⾏粉刷。每次粉刷会等概率选取两个格子，粉刷以这两个格子为顶点的矩形区域。求经过 K 次粉刷后，⾄少被刷了一次的格子数的期望。

## 容斥原理见 [oiwiki](https://oiwiki.com/math/combinatorics/inclusion-exclusion-principle/)。