OI数学专题笔记 - 4

容斥原理

现有 {A1,A2,,An}\{A_1, A_2, \cdots, A_n\} 总共 nn 个集合,一直任意多个子集交集的大小,则所有集合并集的大小为:

\sum_{B\subset\{A_1, A_2, \cdots, A_n\}} (-1)^{|B| + 1} \cdot |\cap_{A_i\inB}A_i|

随机试验

  1. 不能预先确知结果

  2. 实验之前可以预测所有可能结果或范围

  3. 可以在相同条件下重复实验

  • 样本空间:随机试验所有可能结果组成的集合

  • 连续性样本空间(不要求掌握)、离散样本空间、无穷样本空间

随机事件

  • 样本空间的任意一个子集称之为事件

  • 事件发生:在一次试验中,事件的一个样本点发生

  • 必然事件:样本空间全集

  • 不可能事件:空集

事件本身是样本空间的子集,所以事件的运算本质上是集合的运算。

概率

定义:为样本空间的每一个事件定义一个实数,这个实数称为概率。事件 AA 的概率称为 P(A)P(A)

  1. P(A)0P(A) \geq 0

  2. P(A)=1\sum P(A) = 1

  3. 设 $A_1, A_2, \cdots $ 是两两互不相容的事件(互斥事件),则有 P(A1A2)=P(A1)+P(A2)+P(A_1 \cap A_2 \cap \cdots) = P(A_1) + P(A_2) + \cdots

概率的若干性质

  • P()=0P(\empty) = 0

  • A1,A2,,A3A_1, A_2, \cdots, A_3 互不相交,则 P(A1A2An)=P(A1)+P(A2)++P(An)P(A_1 \cup A_2 \cup \cdots \cup A_n) = P(A_1) + P(A_2) + \cdots + P(A_n)

  • 如果 AB,P(BA)=P(B)P(A)A \subset B, P(B - A) = P(B) - P(A)

  • 更一般的, P(BA)=P(B)P(AB)P(B - A) = P(B) - P(AB)

  • 0P(A)10 \leq P(A) \leq 1

  • P(AB)=P(A)+P(B)P(AB)P(A \cup B) = P(A) + P(B) - P(AB)

条件概率

定义:已知事件 BB 发生时,事件 AA 发生的概率为 P(AB)=P(AB)P(B)P(A|B) = \frac{P(AB)}{P(B)}

乘法法则: P(AB)=P(AB)P(B)P(AB) = P(A|B) \cdot P(B)

条件概率性质

  • P(A)=0P(\empty | A) = 0

  • B1,,BnB_1, \cdots, B_n 互不相容,则 P(i=1nBiA)=i=1nP(BiA)P(\cup_{i = 1}^n B_i | A) = \sum_{i = 1}^n P(B_i|A)

  • P(BA)=P(A)P(BA)P(\overline{B} | A) = P(A) - P(B|A)

  • P(BCA)=P(BA)+P(CA)P(BCA)P(B \cup C|A) = P(B|A) + P(C|A) - P(BC|A)

期望

  • E[f(x)]=Σf(x)P(X=x)E[f(x)] = \Sigma f(x)P(X = x)

  • 定理一: E[c1X1+c2X2+]=c1E[X1]+c2E[X2]+E[c_1X_1 + c_2X_2 + \cdots] = c_1E[X_1] + c_2E[X_2] + \cdots

  • 定理二: X1,X2X_1, X_2 独立,则 E[X1X2]=E[X1]E[X2]E[X_1X_2] = E[X_1]E[X_2]

  • 期望的和 = 和的期望

贝叶斯公式

  • B1,B2,,BnB_1, B_2, \cdots, B_n 是样本空间的划分,则有:

P(BiA)=P(ABi)P(Bi)1nP(ABj)P(Bj)P(B_i|A) = \frac{P(A|B_i)P(B_i)}{\sum_1^n P(A|B_j)P(B_j)}

样本空间的划分:
B1B2Bn=U()B_1 \cup B_2 \cup \cdots \cup B_n = U (全集)
B1B2Bn=B_1 \cap B_2 \cap \cdots \cap B_n = \empty