1.1 随机事件及其运算

在相同的条件下重复进行一系列实验和观察，被称为随机试验，简称为试验。

随机试验具有三个特点：可重复、多结果、不确定、具有统计规律性

1.1.1 样本空间与随机事件

• 样本点：随机试验中的每一种可能的结果

• 样本空间：所有样本点组成的集合，记为$\Omega = \{w\}$

• 样本空间的类型：

  • 有限样本空间：样本点的数目是有限的
  • 无限可列样本空间：样本点个数是无限的、但可列的
  • 不可列样本空间：样本点个数是无限的、且不可列的

1.1.2 随机事件的关系与运算

• 包含：事件$A$的发生必然导致事件$B$的发生，记$A \subseteq B$

  • $A = B \ \text{if and only if}\ A \subseteq B \ \text{and} B \subseteq A$

• 并/和：事件$A$和事件$B$至少发生一个，记为$A \cup B$

• 差：事件$A$发生而事件$B$不发生，记为$A - B$

• 交：事件$A$和$B$同时发生，记为$A \cap B\ \text{or} \ AB$

• 互斥：事件$A$和$B$必不可能同时发生，记为$A \cap B = \varnothing$

• 对立：事件$A$不发生的事件，记为$\bar{A}$

  • $A \cap \bar{A} = \varnothing \ \text{and} \ A \cup \bar{A} = \Omega$

运算规律

• 幂等律：$A \cup A = A. A \cap A = A$
• 交换律：$A \cup B = B \cup A, A \cap B = B \cap A$
• 结合律：$(A \cup B) \cup C = A \cup (B \cup C), (A \cap B) \cap C = A \cap (B \cap C)$
• 分配率：$A \cap(B \cup C) = (A \cap B) \cup (A \cap C), A \cup(B \cap C) = (A \cup B) \cap (A \cup C)$
• 对偶率：$\overline{A \cup B} = \bar{A} \cap \bar{B}, \overline{A \cap B} = \bar{A} \cup \bar{B}$

设$A, B, C$为三个随机事件，则有：

• 事件$A$与$B$同时发生，而事件$C$不发生的事件可表示为：$AB\bar{C} = AB - C$
• 三个事件中至少有一个发生的事件可表示为：$A\cup B \cup C$
• 三个事件中恰好有一个发生的事件可表示为：$A\overline{BC} \cup \bar{A}B\bar{C} \cup \overline{AB}C$
• 三个事件中至多有一个发生的事件可表示为：$\overline{AB \cup BC \cup AC}$
• 三个事件中至少有两个发生的事件可表示为：$AB \cup BC \cup AC$
• 三个事件中至多有两个发生的事件可表示为：$\overline{ABC} = \bar{A} \cup \bar{B} \cup \bar{C}$
• 三个事件中恰好有两个发生的事件可表示为：$AB\bar{C} \cup A\bar{B}C \cup \bar{A}BC$

1.1.3 可测空间*（TODO）

1.2 频率与概率公理化

1.2.1 频率

定义 0.1 在相同的条件下，进行了$n$次试验，$n$次试验中事件$A$发生的次数为$m$，则称事件$A$发生的频率为：

事件的频率在一定程度上反映了事件发生的可能性，其性质包括：

• $0 \leq f_n(A) \leq 1$

• $f_n(\Omega) = 1$

• 互斥事件的频率可加：

  $$f_n(A_1 \cup A_2 \cup \cdots \cup A_k) = \sum_{i=1}^k f_n(A_i)$$

定义 0.2 随机事件$A$在大量重复试验中发生的频率总是稳定地在一个常数$p$附近摆动，随着试验次数的增加而摆幅逐渐减小，则称常数$p$为事件$A$发生的概率，记为$P(A) = p$.

概率 VS 频率

概率是用于度量还见发生的可能性，客观上是恒定的。

频率用在一定程度上反映了事件发生的可能性，在试验中具有随机性

频率是概率的一个近似

1.2.2 概率的公理化定义

定义 0.3 概率公理化在可测空间$(\Omega, \Sigma)$上，若函数$P:\Sigma \rightarrow [0, 1]$满足下列条件：

• $0 \leq P(A) \leq 1$
• $P(\Omega) = 1$
• （可列的）互斥事件的概率可加$P(\cup_{i=1}^{\infty} A_i) = \sum_{i=1}^{\infty}P(A_i)$

称$P(A)$为事件$A$的频率，$(\Omega, \Sigma, P)$为概率空间。

其中$\Sigma$是……（TODO）

概率的计算性质

性质 1.1 对于不可能发生的事件$\varnothing$，有$P(\varnothing) = 0$

性质 1.2 对于必然发生的事件$\Omega$，有$P(\Omega) = 1$

性质 1.3 （可列可加性） 若$A_1, A_2, \cdots, A_n$是两两不相容的事件，则$P(\cup_{i=1}^{\infty} A_i) = \sum_{i=1}^{\infty}P(A_i)$

性质 1.4 对任意事件$A$，有$P(\bar{A}) = 1 - P(A)$

性质 1.5 若$B \subseteq A$，有$P(A - B) = P(A) - P(B)$和$P(A) \geq P(B)$

性质 1.6 对于任意随机事件$A$和$B$，有$P(A - B) = P(A) - P(AB) = P(A \cup B) - P(B)$

容斥原理（Inclusion-Exclusion Principle）

对于任意两个随机事件$A$和$B$，有

对于任意三个随机事件$A, B, C$有

对于任意多个随机事件$A_1, A_2, \dots, A_n$，有

容斥不等式

• Union Bounds：对于任意多个随机事件$A_1, A_2, \dots, A_n$，有

  $$P(\cup_{i=1}^n A_i) \leq P(A_1) + P(A_2) + \cdots + P(A_n)$$

  注意：对比 Union Bound 和 1 的大小

• Bonferroni Inequalities：对于任意多个随机事件$A_1, A_2, \dots, A_n$，有

  $$P(\cup_{i=1}^{\infty} A_i) \leq \sum_{i=1}^{\infty}P(A_i)\\ P(\cup_{i=1}^{\infty} A_i) \geq \sum_{i=1}^{n}P(A_i) - \sum_{i < j} P(A_iA_j)\\ P(\cup_{i=1}^{\infty} A_i) \leq \sum_{i=1}^{n}P(A_i) - \sum_{i < j} P(A_iA_j) + \sum_{i < j < k}P(A_iA_jA_k)$$

  该结论可以依次类推。

例题：班上有30名学生。令$A_{ij}$表示"第$i, j$两位生日相同"的事件，问至少有两人同生日的概率上下界是多少？

对于$P(\cup_{i < j} A_{ij})$，

• 上界（一阶）：有$P(\cup_{i < j} A_{ij}) \leq \sum_{i < j}P(A_{ij}) = \binom{2}{30} \frac{1}{365} \approx 1.1918$

• 下界（二阶）：有$P(\cup_{i < j} A_{ij}) \geq \sum_{i < j}P(A_{ij}) - \sum_{(i, j) \neq (p, q), i < j, p < q} P(A_{ij}A_{pq}) = \binom{30}{2} \frac{1}{365} - \binom{\binom{30}{2}}{2}\frac{1}{365^2} = 0.4842$

  其中$\binom{\binom{30}{2}}{2}$表示从30个人里面选两个得到的分组组合中选两个组合。

1.3 古典概型与几何概型

1.3.1 古典概型

定义 0.4 如果试验$E$满足：

• 试验的结果只有有限种可能，即样本空间$\Omega = \{w_1, w_2, \dots, w_n\}$，其中$w_i$为基本事件，
• 每种结果发生的可能性相同，即$P(\{w_i\}) = P(\{w_j\})(i \neq j)$，

则称该类试验为 古典概型，又称 等可能概型。

根据上述定义以及$P(\Omega) = 1$可知：每个基本事件发生的概率为$P(\{w_i\}) = \frac{1}{n}$，若事件$A$包含$k$个基本事件$\{w_{i_1}, w_{i_2}, \dots, w_{i_k} \}$，则事件$A$发生的概率为

这里的$|A|$表示事件$A$包含的事件的个数。

定义 0.5 从一个由两类个体组成的有限总体中，随机地一次性抽取货不放回地抽取指定数量的个体，考察其中某一类个体出现的次数，成为超几何概型。

设一批$N$件产品中有$M$件次品，从$N$件产品中无放回地任选$n$件,记事件$B$为“取出的产品种恰有$m$件次品”,求事件$B$的概率。

概率$P(B)$被称为超几何概率（hypergeometric）

例题：将$n$对夫妻任意分成$n$组，每组一男一女，问至少有一对夫妻被分到同一组的概率是多少？

解：

设$A_i$表示第$i$对夫妻在同一组，求$P(\cup_{i=1}^n A_i)$.

根据容斥原理有$P(\cup_{i=1}^n A_i) = \sum_{i=1}^n P(A_i) - \sum_{i<j}P(A_iA_j) + \cdots + (-1)^{n-1} P(\cap_{i=1}^n A_i)$，其中$P(A_i) = \frac{1}{n},P(A_iA_j) = \frac{1}{n(n-1)}$.因此有：

$$\begin{aligned} P(\cup_{i=1}^n A_i) &= n \frac{1}{n} - \binom{n}{2} \frac{1}{n(n - 1)} + \cdots + (-1)^{k - 1}\binom{n}{k} \frac{(n - k)!}{n!} + \cdots + (-1)^{n-1}\frac{1}{n!}\\ &= 1 - \frac{n!}{(n - 2)!2!}\frac{1}{n(n - 1)} + \cdots + (-1)^{k-1}\frac{n!}{(n-k)!k!}\frac{(n-k)!}{n!} + \cdots + (-1)^{n-1}\frac{1}{n!}\\ &= \sum_{i=1}^n (-1)^{i - 1}\frac{1}{i!} \end{aligned}$$

当$n \rightarrow \infty$时，有$\lim_{n \rightarrow \infty} P(\cup_{i=1}^n A_i) = \lim_{n \rightarrow \infty} \sum_{i = 1}^n (-1)^{i - 1}\frac{1}{i!} = e^{-1}$.

1.3.2 几何概型

古典概型考虑有限的样本空间，即有限个等可能的基本事件，在很多实际应用中受到限制。因此讨论一种新的概型：几何概型

• 样本空间无限可测
• 基本事件等可能性

定义 0.6 在一个测度有限的区域$\Omega$内等可能性投点，落入$\Omega$内的任意子区域$A$的可能性与$A$区域的测度成正比，与$A$的位置与形状无关，这 样的概率模型称之为几何概型。

事件$A$发生的概率为

这里$\mu(\cdot)$表示区域的测度。

例题：两银行经理约定中午12：00 - 13：00 到某地会面，两人到达时间随机，先到者等另一人 15分钟后离开。求两人见面的概率。

1.4 十二重计数（the twelvefold way）

问题简述：将$n$只球放入$m$个箱子，有多少种不同的放法？

问题1：将$n$只不同的球放入$m$个不同的箱子

每个球有$m$个选择，一共有$n$个球，因此总放法是$m^n$种

问题2：将$n$只相同的球放入$m$个不同的箱子，每个箱子至多1球

每个箱子至多有1球，且球相同。因此从$m$个箱子里面选择$n$个箱子来放球，有$\binom{m}{n}$种放法

问题3：将$n$只不同的球放入$m$个不同的箱子，每个箱子至多1球

从$m$个箱子里面选$n$个箱子来放球，按一定次序排序，然后对$n$个小球进行重排，有$\binom{m}{n}n!$种放法

问题4：将$n$只相同的球放入$m$个不同的箱子

整数的有序分解 / 有空的隔板法：把箱子的间隔和球一起打乱，进行排序。一共有$n + m - 1$个元素，总共有$\binom{n + m - 1}{n}$种放法

问题5：将$n$只相同的球放入$m$个不同的箱子，每个箱子至少1球

没空的隔板法：$n$个球有$n - 1$个空格用来$m - 1$块板，总共有$\binom{n-1}{m-1}$种放法

问题6：将$n$只不同的球放入$m$个相同的箱子，每个箱子至少1球

第二类Stirling数：$S(n, m)$

问题7：将$n$只相同的球放入$m$个相同的箱子

无序分解，箱子可放可不放，因此是$\sum_{i=1}^m p(n,m)$

问题8：将$n$只不同的球放入$m$个不同的箱子，每个箱子至少1球

考虑将不同的$n$个球放入$m$个相同的箱子中，因此有$S(n, m)$，再进行全排列，总共有$m!S(n, m)$中放法

问题9：将$n$只不同的球放入$m$个相同的箱子

第二类Stirling数，但是因为箱子可以不放球，因此总种数为$\sum_{i=1}^m S(n, i)$

问题10：将$n$只不同的球放入$m$个相同的箱子，每个箱子至多1球

因为箱子已经无从区分了，并且每个箱子至多只有一个球，因此只有一种可能

问题11：将$n$只相同的球放入$m$个相同的箱子，每个箱子至多1球

因为箱子已经无从区分了，并且每个箱子至多只有一个球，因此只有一种可能

问题12：将$n$只相同的球放入$m$个相同的箱子，每个箱子至少1球

每个箱子至少一球，因此为$p(n, m)$

1. 直线排列

$n$个不同元素中无放回地取出$r$个元素进行排列：有$(n)_r = n(n-1) \dots (n-r+1)$种不同的排法

2. 环排列

$n$个不同的元素无放回地取出$r$个元素，排成一个圆环

• 每一个环排列对应于$r$种不同的直线排列
• 不同的环排列的直线排列互不相同

定义 0.7 从$n$个不同的元素无放回地取出$r$个元素，排成一个圆环，有

种不同的排法，称为环排列数。这里，记号$(n)_r$表示$C_n^r r!$

特别地，$n$个不同元素的环排列数为$(n-1)!$

3. 整数的有序分解

问题4：将$n$只相同的球放入$m$个不同的箱子

• 转化：第一个箱子有$x_1$个球，第二个箱子有$x_2$个球，$\dots$，第$m$个箱子有$x_m$个球，其中$x_1, x_2, \dots, x_m$为非负的整数，并满足

• $n$只相同的球放入$m$个不同的箱子等价于上述方程的非负整数解

定理 0.1 （整数的有序分解：非负解）方程

解的个数为$\binom{n + m - 1}{m - 1}$.

定理 0.2（整数的有序分解：正整数解）方程

解的个数为$\binom{n-1}{m-1}$.

4. 多重组合

• 组合：$n$个不同的元素中无放回地取出$r$个元素，有$\binom{n}{r}$种

• 多重组合：将$n$个不同的元素分成$k$组，组内元素无顺序关系，假设每组分别有$r_1, r_2, \dots, r_k$个元素，即$n = r_1 + r_2 + \cdots + r_k$，则有

  $$\binom{n}{r_1, r_2, \dots, r_k} = \binom{n}{r_1} \binom{n - r_1}{r_2} \binom{n-r_1-r_2}{r_3}\cdots \binom{r_k}{r_k} = \frac{n!}{r_1!r_2! \dots r_k!}$$

  种不同的分组方法，称为$\binom{n}{r_1, r_2, \dots, r_k}$多种组合数。

• 多组合数又称多项式系数，因为

  $$(x_1 + x_2 + \cdots + x_k)^n = \sum_{n = r_1 + r_2 + \cdots + r_k} \binom{n}{r_1, r_2, \dots, r_k}x_1^{r_1}x_2^{r_2}\dots x_k^{r_k}$$

• 组合数本质上也属于多重组合数、

5. 多重排列

多重集：假设集合中的元素可以重复，且重复的元素之间不可分辨

• 例如，多重集$A = \{1, 1, 1, 2, 2, 2, 3, 3, 4\}$

• 多重集$A$有$k$类不同的元素，每类元素的个数分别为$r_1, r_2, \dots, r_k$，即$n = r_1 + \cdots + r_k$。将多重集$A$种的所有元素排列成一排，然后

  • 从$n$个位置中选取出$r_1$个位置放第一类元素
  • 再从剩下的从$n - r_1$个位置中选取出$r_2$个位置放第二类元素
  • $\dots$
  • 最后$r_k$个位置放第$k$类元素

  因此$A$有$\binom{n}{r_1, r_2, \dots, r_k}$种不同的排列方法，即多充组合数

6. 第二类 Stirling 数

定义 0.8 将$n$个不同的元素分成$m$个非空的子集，不同的划分数称为第二类 Stirling 数，记为$S(n, m)$

$S(n, m)$：将$n$个不同的元素分成$m$个非空的子集

• 记$S(0, 0) = 1, S(m, 1) = 1, S(n, n) = 1$
• 当$m > n \geq 1$时，有$S(n, m) = 0$

定理 0.3 对$n \geq m \geq 1$，有

进而，有

证明思路

对于$n \geq m \geq 1$，有$S(n, m) = mS(n-1, m) + S(n-1, m-1)$.

• 如果指定元素$A$单独占用一个集合，那么有子问题$S(n-1, m-1)$.
• 如果指定元素$A$并非单独占用一个格子，将其分到$m$个集合中$\binom{m}{1}$，那么有子问题$S(n - 1, m)$

7. 无序划分

• 问题：将正整数$n$划分成$m$个无序的正整数之和

• 转化：将正整数$n$划分成$m$个无序的正整数之和，等价于

  $$x_1 + x_2 + \cdots + x_m = n \quad s.t. \quad x_1 \geq x_2 \geq \cdots \geq x_m \geq 1$$

• 形式化：将正整数$n$划分为$m$个无序的正整数之和，不同的划分数记为$p(n, m)$

  • 记$p(0, 0) = 1, p(n, 1) = 1, p(n, n) = 1$
  • 当$m > n \geq 1$时，有$p(n, m) = 0$

  定理 0.4（递推关系） 对$n \geq m \geq 1$，有

  $$\begin{cases} p(n, m) = p(n - 1, m - 1) + p(n - m, m)\\ p(n, m) = \sum_{i=1}^m p(n - m, i) \end{cases}$$

证明思路

对$n \geq m \geq 1$，有$p(n, m) = p(n-1, m - 1) + p(n - m, m)$

• 如果有单元素的划分，那么有子问题“$n-1$个球装$m-1$个箱子”：$p(n-1, m-1)$
• 如果无单元素划分，默认所有箱子都有一个球了，则所有划分的子集内元素数量减1，那么有子问题“把剩下的$n - m$个球装$m$个箱子”：$p(n- m, m)$

定理 0.5 对正整数$n \geq 1$和$m \geq 1$，有

给定$m \geq 1$，当$n$非常大或趋于无穷的极限中有