第 1 章 概率论导论
1.2 概率的不同类型
直观概率：基于直观来处理判断
古典概率：事件概率不是实验性的，通过预先计算事件 $E$ 可能发生的次数 $n_E$ 形成一个比值 $n_E / n$ 其中 $n$ 是所有可能的结果。此时需要所有的结果是等可能的。
古典概率不能处理实验结果不是等可能的情况，不能处理实验结果是无穷大的情况。
频率作为概率的测度：
$$P[E] = \lim_{n \to \infty} \frac{n_E}{n}$$但注意到 $n$ 不可能是无穷大，因此引入基于公理化理论的概率。
1.4 集合、域和事件
样本空间：所有实验结果的集合 $\Omega$
事件：样本空间的子集
单一实验结果：$\zeta$
$\Omega$ 本身也称必然事件，空集 $\phi$ 也称零事件。
如果 $\Omega = \lbrace \zeta_{1},\zeta_{1},\dots,\zeta_{N} \rbrace$ 则其子集有 $2^N$ 个。
德摩根（De Morgan）定律：
$$\complement_{U}\left[\bigcup_{i=1}^{n} E_i\right] = \bigcap_{i=1}^{n} \complement_{U} E_i$$ $$\complement_{U}\left[\bigcap_{i=1}^{n} E_i\right] = \bigcup_{i=1}^{n} \complement_{U} E_i$$$\sigma$ 域：考虑一个全集 $\Omega$ 和 $\Omega$ 的子集构成的集合簇，另 $E$ 和 $F$ 是这个簇中的任意两个子集，如果
(1) $\phi \in \mathscr{M}$ ，$\Omega \in \mathscr{M}$
(2) 如果 $E \in \mathscr{M}$ 和 $F \in \mathscr{M}$，那么 $E \cup F \in \mathscr{M}$ 和 $E \cap F \in \mathscr{M}$
(3) 如果 $E \in \mathscr{M}$ ，则 $\complement_{\Omega} E \in \mathscr{M}$
则该集合簇形成了一个域 $\mathscr{M}$。
当 $\Omega$ 是不可数的，并非每个子集都能以一致的方式赋予概率（可测的），必须使用较小的集合簇来形成 $\sigma$ 域。比如当 $\Omega = R^1$ 即实数直线时，并非 $\Omega$ 的每个子集都能以一致的方式赋予概率（可测的）。我们可以从所有的开或闭区间生成一个 $\sigma$ 域，即实数直线上的事件的博雷尔（Borel）域，这个域包含了所有感兴趣的工程和科学中的子集。
1.5 概率的公理化定义
概率是一个集合函数 $P[\ \cdot \ ]$ 它对每个事件 $E \in \scr{F}$ 指定一个数 $P[E]$，这个数称为事件 $E$ 的概率，它满足：
(1) $P[E] \ge 0$
(2) $P[\Omega] = 1$
(3) $P[E \cup F] = P[E] + P[F]$ 如果 $E \cap F = \phi$
一些推论
(4) $P[\phi] = 0$
(5) $P[E \cap \left(\complement_{\Omega} F \right)] = P[E] - P[EF]$
(6) $P[E] = 1 - P[\complement_{\Omega} E]$
(7) $P[E \cup F] = P[E] + P[F] - P[EF]$
(8) $P \left[ \cup_{i=1}^{n} E_i \right] = \sum_{i=1}^{n} P[E_i]$ 如果 $\forall \ i \ne j, E_i E_j = \phi$
(9) $P \left[ \cup_{i=1}^{n} E_i \right] \le \sum_{i=1}^{n} P[E_i]$
在一给定实验中，事件 $E_1, E_2, \cdots, E_n$ 至少有一个发生的概率可以用容斥原理来求。
1.6 联合概率、条件概率、全概率和独立性
联合概率：多个事件同时发生的概率。如 $P[AB]$
条件概率：某事件 $A$ 已经发生时 $B$ 发生的概率。
$$P[B|A] = \frac{P[AB]}{P[A]}$$事件独立：如果 $A \in \scr{F}$，$B \in \scr{F}$，且 $P[A] > 0$，$P[B]>0$，当且仅当 $P[AB] = P[A]P[B]$ 时，称事件 $A$ 和 $B$ 是独立的。
一般的，对于独立事件 $P[A|B] = P[A]$，$P[B|A]=P[B]$
联合独立：令 $A_i(i=1,\cdots,n) \in \scr{F}$ 当且仅当
$P[A_i A_j] = P[A_i] P[A_j]$
$P[A_i A_j A_k] = P[A_i] P[A_j] P[A_k]$
$\vdots$
$P[A_1 \cdots A_n] = P[A_1] \cdots P[A_n]$
对所有下标 $1\le i < j < k < \cdots \le n$ 成立时，我们说所有的 $A_i$ 是联合独立。
独立实验：一个实验的结果不受另一个的过去、现在和将来的实验结果的影响。
对于两个实验，如果：
(1) 对于互积事件 $E = E_1 E_2$，我们能够写成
$$P[E] = P_1[E_1] P_2[E_2]$$(2) 在复合实验中，一般事件 $E$ 的概率能够根据单一事件的概率来表示
$$P[E] = \sum_{(\zeta_1, \zeta_2) \in E} P_1[\{ \zeta_1 \}] P_2[\{ \zeta_2 \}]$$则称两个实验是独立的。
推广到 $n$ 个实验的组合，则复合实验的样本空间为
$$\begin{align} \Omega =& \bigotimes_{i=1}^{n} \Omega_i \\ =& \Omega_1 \times \Omega_2 \times \cdots \times \Omega_n \end{align}$$实验结果是一个 $n$ 维向量 $\zeta = (\zeta_1, \zeta_2, \cdots , \zeta_n) \in E \subseteq \Omega$。
事件是独立的，指对于复合实验中的任意事件 $E$
$$P[E] = \sum_{i=1}^{k} P_1[E_{1,i}] P_2[E_{2,i}] $$其中 $E = \bigcup_{i=1}^{k} E_{1,i} \times E_{2,i}$，是一个互不相交的并集，因此概率具有可加性。
非独立实验：第二个实验的概率依赖于第一个实验发生的事件。第二个实验的概率测度需要添加与第一个实验结果相关的下标 $E_{2,i}$。此时对于复合事件 $E$，另 $E_1 = \cup_{i} {\zeta_{1,i}}$
$$P[E] = \sum_{i} P[{\zeta_{1,i}}] P_{2,i}[E_2]$$全概率定理：
令 $A_1, A_2, \cdots, A_n$ 是 $n$ 个互斥的事件，且 $\bigcup_{i=1}^{n} A_i = \Omega$，令 $B$ 是任何一个定义在 $A_i$ 的概率空间上的事件，那么对于所有 $i$，$P[A_i] \neq 0$，有
$$P[B] = \sum_{i=1}^{n} P[B|A_i] P[A_i]$$1.7 贝叶斯定理及其应用
贝叶斯定理(Bayes’ Theorem)：令 $A_i(i=1,2,\cdots,n)$ 是定义在概率空间 $\scr{P}$ 上的一个事件集合，且对于所有的 $i \neq j$，$\bigcup_{i=1}^{n} A_i = \Omega$ 且 $A_i A_j = \phi$。有一个定义在 $\scr{P}$ 上的事件 $B$，$P[B] > 0$ 和对所有 $i$，$P[A_i] \neq 0$，有
$$P[A_j|B] = \frac{P[B|A_j]P[A_j]}{\sum_{i=1}^{n} P[B|A_i] P[A_i]}$$可以发现
$$\frac{P[B|A_j]P[A_j]}{\sum_{i=1}^{n} P[B|A_i] P[A_i]} = \frac{P[A_j B]}{P[B]}$$1.8 组合
容量为 $r$ 的有序样本：$n$ 个元素 $a_1, a_2, \cdots, a_n$ 的任何有序排列 $a_{k_1}, a_{k_2}, \cdots, a_{k_r}$，其中每个 $k_i$ 可以是 $1$ 到 $n$ 的任意值。
重复抽样能够形成 $n^r$ 个不同的有序样本。
无重复抽样能够形成
$$(n)_r = \frac{n!}{(n-r)!} = C_n^r \cdot r!$$对于组合数 $C_n^r$ 由于其也为二项式系数，也记作
$$C_n^r = \binom{n}{r}$$由于 $n$ 个元素自己的数目是 $2^n$ 个，因此
$$\sum_{r=0}^{n} \binom{n}{r} = 2^n$$把 $n$ 个元素集合划分成 $l$ 个大小为 $r_1, r_2, \cdots, r_l$ （$\sum_{i=1}^{l} r_i = n$）的不同集合的方案数有
$$\binom{n}{r_1}\binom{n-r_1}{r_2} \cdots \binom{n-r_1-r_2-\cdots - r_{l-1}}{r_l} = \frac{n!}{r_1! \cdot r_2! \cdots r_l!} = \binom{n}{r1 \ r2 \ \cdots \ r_l}$$入住问题：$r$ 个球放入 $n$ 个盒子，
-
盒子可辩别，球可辩别，方案数为 $n^r$
-
盒子可辩别，球不可辩别。考虑隔板法，即在 $r$ 个球前后及之间的空隙插入 $n-1$ 个隔板。由于隔板和球都是不可区分的，而隔板和球的顺序可以是任意的，这相当于从 $n-1+r$ 个隔板或球中选出球或隔板，即：
- 盒子可辩别，球不可辩别，盒子不能为空。此时隔板之间必须有球，相当于直接向隔板之间的空隙插入球即可，即
生日碰撞：
记一年天数为 $n$，一个组中有 $r$ 个人，用 $P_0(r,n)$ 表示一组中没有人生日相同的概率，则
$$P_0(r,n) = \frac{n(n-1)(n-2)\cdots(n-r+1)}{n^r} = \prod_{i=1}^{r-1} (1-\frac{i}{n})$$1.9 伯努利试验（Bernoulli Trials）：二项式和多项式的概率分布
伯努利试验（Bernoulli Trials）：只有成功 $s$ 失败 $f$ 两种可能，有 $P[s] = p,P[f]=q$，其中 $0<p<1,q=1-p$
假定该试验做了 $n$ 次，则样本空间为：
$$\Omega_n = {a_1,\cdots, a_M}$$其中 $M=2^n$，$a_i$ 是一个有序的 $n$ 元组。
$n$ 试验 $k$ 次成功的概率，即二项式概率分布律
$$b(k;n,p) = \binom{n}{k} p^k q^{n-k}$$$n$ 试验小于等于 $k$ 次成功的概率，即二项式分布函数
$$B(k;n,p) = \sum_{i=0}^{k} b(i;n,p) = \sum_{i=0}^{k} \binom{n}{k} p^i q^{n-i}$$多项式概率分布
多项式概率分布是二项式概率分布的推广。假设某次试验有 $l$ 个结果，对应结果 $\zeta_i$ 的概率为 $p_i$， 那么有，$p_i \ge 0, \sum_{i=1}^{l} p_i = 1$
$n$ 次试验结果构成一个 $n$ 长的有序串，其中 $\zeta_i$ 出现 $r_i$ 次，则此实验结果出现的概率为
$$\prod_{i=1}^{n} p_i^{r_i}$$如果忽略结果的有序性，只在乎每种 $\zeta_i$ 的出现次数为 $r_i$ 次，则概率为
$$\binom{n}{r1 \ r2 \ \cdots \ r_l}\prod_{i=1}^{n} p_i^{r_i}$$1.10 二项式概率分布的渐进特性：泊松分布（Poisson Law）
假定二项式函数 $b(k;n,p)$ 中 $n \gg 1, p \ll 1$， 但 $np = \mu$ 保持一个常数，则
$$b(k;n,p) = \binom{n}{k} p^k q^{n-k} \approx \frac{1}{k!} \mu^k \left(1-\frac{\mu}{n} \right)^{n-k}$$当 $n \rightarrow \infty$ 时，
$$\frac{1}{k!} \mu^k (1-\frac{\mu}{n})^{n-k} \rightarrow \frac{\mu^k}{k!} e^{-\mu}$$参数为 $\mu > 0$ 的泊松分布为
$$\frac{\mu^k}{k!} e^{-\mu}, \quad 0 \le k < \infty$$1.11 二项式分布近似为正态分布
定义 $f_{SN}(x)$ 为标准正态分布，
$$f_{SN}(x) = \frac{1}{\sqrt{2\pi}} \exp \left(-\frac{1}{2}x^2 \right) $$当 $n$ 很大时，尤其是 $npq \gg 1$ 时，
$$b(k;n,p) \approx \frac{1}{\sqrt{npq}} f_{SN} \left(\frac{k-np}{\sqrt{npq}} \right) $$Next: 《C++ Primer》 拾遗 第 1 章 开始