概率与期望

· · 算法·理论

1 事件与概率

1.1 相关概念

1.1.1 事件

  1. 基本事件：由一个样本点组成的只有一个元素的集合。
  2. 必然事件：在某种条件下必然会发生的事件。
  3. 不可能事件：在某种条件下一定不会发生的事件
  4. 随机事件：在某种条件下不一定发生的事件。 必然事件和不可能事件统称确定事件，确定事件与随机事件统称事件。

1.1.2 频数、频率与概率

  1. 频数：在相同条件下进行 n 次试验，观察某一事件 A 是否发生，称 n 次试验中 A 的发生次数为 A 的频数，记作 n_A。
  2. 频率：在频数的基础上，称 A 出现的比例 \dfrac{n_A}{n} 为事件 A 的频率。
  3. 概率：对于一个事件，其频率 \dfrac{n_A}{n} 随着试验次数增加而不断趋定于某个值，称之为 A 发生的概率。记作 P(A)。

1.2 事件的关系与运算

如下表所示：

名称 定义 符号
包含关系 若事件 A 发生时，事件 B 一定发生，则称事件 B 包含事件 A B\supseteq A
相等关系 若 A\supseteq B \wedge B\supseteq A，则称事件 A 与事件 B 相等 A=B
并事件（和事件） 若某事件发生 \Leftrightarrow 事件 A \vee 事件 B 发生，则称该事件为 A,B 的和事件 A+B 或 A\bigcup B
交事件（积事件） 若某事件发生 \Leftrightarrow 事件 A \wedge 事件 B 发生，则称该事件为 A,B 的积事件 A\times B 或 A\bigcap B
互斥事件 若 A\bigcap B 为不可能事件，则称 A,B 互斥 /
对立事件 若 A\bigcap B 为不可能事件，A\bigcup B 为必然事件，则称 A,B 为对立事件 /

2 概率公式

2.1 条件概率

我们记 P(B|A) 表示在事件 A 发生的前提下，事件 B 发生的概率。

请注意：这里是假设 A 发生的前提下，而并非 A 实际发生。

那么如何计算条件概率呢？当 P(A)>0 时，我们有：

P(B|A)=\dfrac{P(AB)}{P(A)}

同时我们有会有推论：当且仅当 A,B 事件独立时，P(B|A)=P(B) 。

证明如下：

首先证 \Rightarrow 。

当事件 A,B 独立时，有 P(AB)=P(A)P(B)。

因此这时有 P(B|A)=\dfrac{P(AB)}{P(A)}=\dfrac{P(A)P(B)}{P(A)}=P(B)。

接下来证 \Leftarrow。

若 P(B|A)=P(B)，则 \dfrac{P(AB)}{P(A)}=P(B)，即 P(AB)=P(A)P(B)。

因此 A,B 事件独立。

证毕。

再次由条件概率公式，将分母移到左边可得：

P(AB)=P(A)P(B|A)

这被称之为概率的乘法公式。

2.2 全概率公式

对于若干事件 A_1,A_2\cdots,A_n 两两互斥，同时满足 A_1\bigcup A_2\bigcup\cdots\bigcup A_n=\Omega，且 P(A_i)>0 ，则对于事件 B\subseteq\Omega，有：

P(B)=\sum_{i=1}^nP(A_i)p(B|A_i)

这被称作全概率公式，是概率论中最基础的公式之一。

全概率公式用于：导致一件事情发生的原因有很多（原因互斥），求其发生的概率。

2.3 贝叶斯公式

对于若干事件 A_1,A_2\cdots,A_n 两两互斥，同时满足 A_1\bigcup A_2\bigcup\cdots\bigcup A_n=\Omega，且 P(A_i)>0 ，则对于事件 B\subseteq\Omega，有

P(A_i|B)=\frac{P(A_iB)}{P(B)}=\frac{P(A_i)P(B|A_i)}{P(B)}=\frac{P(A_i)P(B|A_i)}{\sum\limits_{k=1}^nP(A_k)P(B|A_k)}

贝叶斯公式可以用于：导致一件事情发生的原因有很多（原因互斥），求这件事情已经发生后，是某个原因导致的概率。

3 期望

3.1 定义

事件 A 有多种结果，记其结果的大小为 x，则 x 的期望值表示事件 A 的平均大小，记作 E(x)。

## 3.2 性质 期望具有线性性质。 * 对于随机变量 $x,y$ 与常量 $a,b$ ，有 $E(ax+by)=aE(x)+bE(y)$。 * 当随机变量 $x,y$ 相互独立时，有 $E(xy)=E(x)E(y)

在一般情况下，求解概率时正推，求解期望时逆推。