目录
- 概述
- 概率
- 概率相关的概念
- 概率的意义
- 同时发生的概率
- 概率的公理 & 命题
- 条件概率
- 概念
- 全概率公式
- 贝叶斯公式
- 例题
- 随机变量
- 概率在 OI 中的应用
- 数学期望
- 数学期望的概念
- 数学期望的线性性 & 递推
- 数学期望在 OI 中的应用
概述
数学在 OI 中占了很大的比例，其中主要包含数论、组合数学和概率期望的内容。推荐读者先进行排列组合的学习再来阅读本文章。这篇文章，我会来好好讲讲概率期望是怎么一回事。我会通过数学的概念和 OI 的题目来进行阐述。我学习的概念都来自于《概率论基础教程》——《A First Course in Probability》，读者有兴趣了解更多内容就可以去看一看。
概率
概率相关的概念
样本空间：在试验中所有可能的结果构成的集合就叫做该试验的样本空间，一般记为\(S\)。
事件：样本空间内的子集叫做事件，如果一次试验中的结果包含了事件，我们就乘事件发生了。一般记为\(E\)，可以作为一个集合来进行理解，比如说硬币两枚硬币至少有一个向上的事件可以记为\(E=\{ (Up,Down),(Up,Up),(Down,Up) \}\)。
互不相容的事件：如果有两个事件\(E_1,E_2\)且\( E_1 \cap E_2 \)，则称事件\(E_1,E_2\)是互不相容的。
补集转化：在一个集合内，如果我们难以统计答案集合\(S_{ans}\)，我们可以统计其补集然后使用容斥定理进行补集转化，求得其补集\(S_{rev}\)，则答案集合为\(S_{ans}=S-S_{rev}\)。
概率：可以近似为一个试验中某个事件占总结过的比例。所以，\[P(E)=\lim_{n \to \infty} \frac{n(E)}{n} \]其中\(n(E)\)代表\(n\)次事件中发生的次数。但是，理论上的和试验上的总是会有偏差，为了保证数学的严谨性，就直接把概率定义为这个。
概率的意义
概率是一个非常玄学的东西，我们来解释下上面那个公式：\[P(E)=\lim_{n \to \infty} \frac{n(E)}{n} \]
这上面的公式中，\(P\)代表某个试验，其中\(P(E)\)代表事件\(E\)在试验中的概率，也就是在一定试验次数内事件\(E\)发生的次数比上该次试验次数。随着试验次数\(n\)趋近于无限，概率也就会越来越精确。
同时发生的概率
我们现在有两个事件\(E,F\)，则我们记这两个事件同时发生的概率为\(P(E \cap F)\)，亦记作\(P(EF)\)。其中，\(EF\)定义为\( E \cap F \)，即为两个事件的交。
概率的公理 & 命题
公理 1
\[0 \leq P(E) \leq 1\]
公理 2
对于试验\(P\)，它样本空间的概率为：\[P(S)=1\]
公理 3
对于一系列互不相容的事件集\(E_1,E_2,\dots\)，也就是\(\forall i,j,E_i \cap E_j = \emptyset \)，有
\[ P(E_1 \cup E_2 \cup E_3 \cup \dots) = \sum_{i=1}^{\infty}P(E_i) \]
其中，每一个概率只有在满足上述这三条公理情况下才能算作概率。
命题 1
对于\(P(E \cup F)\)，有公式：
\[ P(E \cup F) = P(E) + P(F) – P(EF) \]
可以用 Venn 图证明。
条件概率
概念
顾名思义，条件概率这个概念是在研究条件发生时事件发生的概率。我们把事件\(E\)在事件\(F\)发生下发生概率记为\(P(E|F)\)。其中，有公式
\[ P(E|F) = \frac {P(EF)}{P(F)} \]
个人理解：事件\(E\)在事件\(F\)发生的情况下，样本容量就从\(1\)缩小成了\(P(F)\)，然后同时发生的概率为\(P(EF)\)，自然在条件（\(F\)发生了）的情况下，概率会变成发生的概率对样本容量的占比。
例题 2a (原书 Page 49)
乔伊80%肯定他把失踪的钥匙放在了他外套两个口袋中的一个。他40%确定在放在左口袋，40%确定放在有口袋。如果检查了左口袋发现没有找到钥匙，那么钥匙在右口袋的概率是多少？
这是一道经典的条件概率题，定义\(R,L\)为把钥匙放在左、右口袋这两个事件，我们可以首先列出式子：
\[ P(R|L^c) = \frac{P(RL^c)}{P(L^c)} \]
其中事件交\(RL^c\)的运算结果为\(R\)，化简为：
\[ =\frac{P(R)}{1-P(L)} \]
结果则显而易见。
全概率公式
考虑我们有样本空间的划分：\[ E_1, E_2, \dots, E_n, \forall E_i \cap E_j = \emptyset, \bigcup_i E_i = U \]
我们可以感性的推出一个式子：
\[ P(E) = \sum_i P(E|E_i)*P(E_i) \]
这就是著名的全概率公式。我们可以从这个角度来理解这个公式：对于一个事件发生的概率，其实等价于在任何情况下发生的概率，等于每种情况下发生的并，很好理解。有的时候做题可以这样来搞。
贝叶斯公式
贝叶斯公式长这个样子：
\[ P(A|B) = \frac{P(AB)}{P(B)} = \frac{P(B|A)P(A)}{P(B)} \]
这个其实只需要在条件概率上面迁移一下即可证明。\(P(AB) = P(B|A)P(A)\)可以理解为在\(A\)发生的情况下\(B\)发生的概率在\(A\)发生的情况下的概率。这个是等价的。