1 基本概念
1.1 概率空间
离散概率空间 $(\Omega, \Pr)$ 由一个非空可数集合 $\Omega$ 和定义在其上的 概率质量函数（pmf）$\Pr: \Omega \to \mathbb{R}$ 组成。要求 $\forall \omega \in \Omega, \Pr[\omega] \geq 0$ 且 $\sum_{\omega \in \Omega} \Pr [\omega] = 1$。每一个 $\omega \in \Omega$ 被称为一个 样本点。
1.2 事件
事件是非空可数集合 $\Omega$ 的一个子集（因此也必然是可数的）。事件 $A$ 发生的概率被定义为：
$$
\Pr[A] := \sum_{\omega \in A} \Pr[\omega]
$$
事件的组合通常用逻辑运算符号来描述，如 $A \wedge B$，$A \vee B$，$\lnot A$ 等。下面给出了事件组合的一些性质：
-
相交：如果
$A \wedge B = \varnothing$，那么我们称事件$A$和$B$是不相交的（disjoint）；否则事件$A$和$B$相交。 -
独立：事件
$A$和$B$是独立的（independent）当且仅当$\Pr[A \wedge B] = \Pr[A] \cdot \Pr[B]$。 -
相互独立：事件的集合
$\{A_i \mid i \in I \}$相互独立（fully / mutually independent）当且仅当$$ \Pr \bigg[\bigwedge_{i=1}^n A_i\bigg] = \prod_{i=1}^n \Pr[A_i] $$ -
成
$k$对独立：如果事件的集合$\{A_i \mid i \in I \}$的每一个由$k$个事件组成的子集都是相互独立的，则称$\{ A_i \mid i \in I \}$是成$k$对独立的（$k$-wise independent）；当$k=2$时，我们称$\{ A_i \mid i \in I \}$是成对独立的（pairwise independent）。若$\forall k$均有$\{ A_i \mid i \in I \}$是成$k$对独立的，则$\{ A_i \mid i \in I \}$是相互独立的。 -
条件概率：对于任意两个事件
$A$和$B$且$\Pr[B] > 0$，则在$B$发生的条件下$A$发生的概率为$$ \Pr[A \mid B] = \frac{\Pr[A \wedge B]}{\Pr[B]} $$
1.3 组合事件的一些恒等式
-
Union Bound：对于任意事件
$A_1, A_2, ..., A_n$有$$ \Pr \bigg[\bigwedge_{i=1}^n A_i\bigg] \leq \prod_{i=1}^n \Pr[A_i] $$ -
Disjoint Union：如果事件
$A_1, A_2, ..., A_n$是成对不相容的，即$\forall i \neq j, A_i \wedge A_j = \varnothing$，则$$ \Pr \bigg[\bigvee_{i=1}^n A_i\bigg] = \sum_{i=1}^n \Pr[A_i] $$ -
The Principle of Inclusion-Exclusion：对于任意有穷事件集合
$\{A_1, A_2, ..., A_n\}$，有$$ \Pr \bigg[\bigvee_{i=1}^n A_i\bigg] = 1 - \sum_{I \subseteq \{1, ..., n\}} (-1)^{|I|} \Pr \bigg[\bigwedge_{i \in I} A_i \bigg] $$当$n=2$时，有$$ \Pr [A \vee B] = \Pr [A] + \Pr [B] - \big( \Pr [A \wedge B] \big) $$ -
Independent Union：如果有穷事件集合
$\{A_1, A_2, ..., A_n\}$是相互独立的，$$ \Pr \bigg[\bigvee_{i=1}^n A_i\bigg] = 1 - \prod_{i=1}^n \bigg( 1 - \Pr[A_i] \bigg) $$当$n=2$时，有$$ \Pr [A \vee B] = 1 - (1 - \Pr [A]) (1 - \Pr [B]) $$ -
Bayes’ Theorem：对于任意事件
$A$和$B$，如果$\Pr[A] \neq 0, \Pr[B] \neq 0$，则根据条件概率的定义可得$$ \Pr[A \mid B] \Pr [B] = \Pr [A \wedge B] = \Pr [A] \cdot \Pr [B] = \Pr[B \mid A] \Pr [A] $$ -
Law of Total Probability：设
$\{B_n : n = 1, 2, ... \}$是概率空间$\Omega$的有限或可数无限的分隔，且每个集合可数，则对任意事件$A$有$$ \Pr [A] = \sum_{n} \Pr[A \wedge B_n] = \sum_{n} \Pr [A \mid B_n] \Pr [B_n] $$
1.4 随机变量
随机变量 $X$ 是一个从 $\Omega$ 到某个数值集合 $V$ 的一个映射：$X(\omega \in \Omega) = x \in V$。随机变量既不随机，也不是一个变量，而是一个函数。 显然，有
$$ \Pr [X = x] = \Pr [A := \{ \omega \in \Omega \mid X(\omega) = x \}] $$
定义在随机变量上的任意概念总应当回归到事件这一底层概念上去理解。
随机变量 $X$ 的（累积）分布函数 CDF 如下：
$$ \textrm{CDF}_X (X \leq x) = \Pr[X \leq x] = \Pr [A := \{ \omega \in \Omega \mid X(\omega) \leq x \}] $$
1.5 期望
定义在随机变量 $X$ 上的期望为：
$$ \begin{aligned} (\textrm{离散}) \qquad &\mathbb{E} [X] := \sum_{x} x \cdot \Pr [X = x] \\ (\textrm{连续}) \qquad &\mathbb{E} [X] := \int_{-\infty}^{\infty} x f_X (x) dx \end{aligned} $$
其中 $f_X (\cdot)$ 是随机变量 $X$ 的概率密度函数。
若 $X$ 为任意整数随机变量，则
$$ \mathbb{E} [X] = \sum_{x \geq 1} \bigg( \Pr[X \geq x] - \Pr[X \leq -x] \bigg) $$
这个结论可以通过 $\Pr[X = x] = \Pr[X \geq x] - \Pr [X \geq x + 1]$ 这个等价代换来证明。
1.6 条件期望
事件 $A$ 发生的情况下随机变量 $X$ 的条件期望为：
$$ \begin{aligned} \mathbb{E} [X \mid A] &:= \sum_{x} x \cdot \Pr [X = x \mid A] = \sum_{x} \frac{x \cdot \Pr [X = x \wedge A]}{\Pr [A]} \\ &= \sum_{x} \frac{x \cdot \Pr [\{ \omega \in A \mid X(\omega) = x \}]}{\Pr [A]} \end{aligned} $$
1.7（离散变量的）全期望展开
对于任意事件 $A$（或随机变量 $A$），下面两个式子成立：
$$ \begin{aligned} &\mathbb{E} [X] = \mathbb{E} [X \mid A] \cdot \Pr [A] + \mathbb{E} [X \mid \lnot A] \cdot \Pr [\lnot A] \\ &\mathbb{E} [X] = \sum_{a} \mathbb{E} [ X\mid A = a ] \cdot \Pr [A = a] \end{aligned} $$
1.8 联合概率（以连续变量为例）
-
联合分布函数：设二元随机变量
$(X,Y)$的分布函数为$\textrm{CDF} (x,y)$，其联合概率密度函数为$f(x,y)$，则有$$ \begin{aligned} &\textrm{CDF}(x,y) = \Pr [X \leq x, Y \leq y] = \int_{-\infty}^x \int_{-\infty}^y f(u,v) du dv \\ &\textrm{CDF}(\infty, \infty) = 1 \end{aligned} $$ -
边缘分布函数：
$$ \begin{aligned} &\textrm{CDF}_X (x) = \Pr [X \leq x] = \int_{-\infty}^x \int_{-\infty}^\infty f(u,v) du dv = \textrm{CDF}(x, \infty) \\ &\textrm{CDF}_Y (y) = \Pr [Y \leq y] = \int_{-\infty}^\infty \int_{-\infty}^y f(u,v) du dv = \textrm{CDF}(\infty, y) \end{aligned} $$ -
边缘密度函数：
$$ \begin{aligned} f_X (x) &= \lim_{\Delta x \to 0} \frac{\textrm{CDF}_X (x + \Delta x) - \textrm{CDF}_X (x) }{\Delta x} \\ &= \lim_{\Delta x \to 0} \frac{\int_{x}^{x + \Delta x} \int_{-\infty}^\infty f(u,v) du dv}{\Delta x} \\ &= \int_{-\infty}^\infty f(x,v) dv \end{aligned} $$同理有$$ \begin{aligned} f_Y (y) = \int_{-\infty}^{\infty} f(u,y) du \end{aligned} $$ -
条件密度函数：在
$Y=y$的条件下，$X$的条件密度函数记为$f_{X|Y} (x \mid y)$，则$$ \begin{aligned} f_{X|Y} (x \mid y) &:= \lim_{\Delta x \to 0} \frac{\Pr[x \leq X \leq x + \Delta x \mid Y = y]}{\Delta x} \\ &= \lim_{\Delta x \to 0} \lim_{\Delta y \to 0} \frac{\Pr [x \leq X \leq x + \Delta x, y \leq Y \leq y + \Delta y]}{\Delta x \Pr [y \leq Y \leq y + \Delta y]} \\ &= \lim_{\Delta x \to 0} \lim_{\Delta y \to 0} \frac{\int_{x}^{x + \Delta x} \int_{y}^{y + \Delta y} f(u, v) du dv}{\Delta x \int_{-\infty}^\infty \int_{y}^{y + \Delta y} du dv} \\ &= \frac{\int_y^{y + \Delta y} f(x, v) dv}{\int_{-\infty}^\infty \int_{y}^{y + \Delta y} du dv} = \frac{\frac{\int_y^{y + \Delta y} f(x, v) dv}{\Delta y}}{\frac{\int_{-\infty}^\infty \int_{y}^{y + \Delta y} du dv}{\Delta y}} \\ &= \frac{f(x,y)}{\int_{-\infty}^\infty f(u,y) du} = \frac{f(x,y)}{f_Y (y)} \end{aligned} $$ -
联合概率密度：由上可知，对于两个连续的随机变量
$X$和$Y$，它们的联合概率密度为$$ \begin{aligned} f(x,y) = f_{X|Y} (x \mid y) f_Y(y) = f_{Y|X} (y \mid x) f_X(x) \end{aligned} $$ -
条件期望：
$$ \mathbb{E}_X [X \mid Y = y] := \int_{-\infty}^\infty x f_{X|Y}(x \mid y) dx = \int_{-\infty}^\infty x \frac{f(x,y)}{f_Y(y)} dx $$且有
$$ \begin{aligned} \mathbb{E}_Y \big[\mathbb{E}_X [X \mid Y]\big] &= \int_{-\infty}^\infty \mathbb{E}_X [X \mid Y] f_Y (y) dy = \int_{-\infty}^\infty \int_{-\infty}^\infty x f_{X|Y} (x \mid y) dx f_Y (y) dy \\ &= \int_{-\infty}^\infty x \int_{-\infty}^\infty f_{X|Y} (x \mid y) f_Y (y) dy dx \\ &= \int_{-\infty}^\infty x \bigg[ \int_{-\infty}^\infty f(x, y) dy \bigg] dx \\ &= \int_{-\infty}^\infty x \big[ f_X(x) \big] dx = \mathbb{E}_X [X] \end{aligned} $$这就是**（连续变量的）全期望展开**。同理可得：$\mathbb{E}_X \big[\mathbb{E}_Y [Y \mid X]\big] = \mathbb{E}_Y [Y]$。
1.9 随机变量的独立性及其特征
-
随机变量的独立性（由事件的独立性引申而来）： 如果对于任意的
$x$和$y$，事件$\{\omega \in \Omega \mid X(\omega) = x \}$和事件$\{\omega \in \Omega \mid Y(\omega) = y \}$是独立的，即$$ \Pr [X = x \wedge Y = y] = \Pr [X = x] \cdot \Pr [Y =y] $$或
$$ \Pr [X = x \mid Y = y] = \Pr [X = x] $$对任意的$x$和$y$恒成立，则称随机变量$X$和$Y$独立。这意味着，知道其中一个随机变量的取值不会对知道另一个随机变量的分布有任何帮助。一组随机变量
$X_1,X_2,...,X_n$相互独立当且仅当对于任意的$x_1,x_2,...,x_n$有$$ \begin{aligned} \Pr \bigg[\bigwedge_{i=1}^n \big( X_i = x_i \big) \bigg] = \prod_{i=1}^n \Pr [X_i = x_i] \end{aligned} $$ -
对期望的影响（以离散变量为例）：如果定义在实数域的随机变量
$X$和$Y$独立，则$$ \begin{aligned} \mathbb{E} [X \cdot Y] &= \sum_{x} \sum_y \Pr [X = x, Y=y] \\ &= \sum_{x} x \Pr [X = x] \cdot \sum_y y \Pr [Y = y] = \mathbb{E} [X] \cdot \mathbb{E}[Y] \end{aligned} $$且对于任意给定函数$f$，都有$f(X)$和$f(Y)$独立。反之不一定成立。同理，如果定义在实数域的一组随机变量
$X_1,X_2,...,X_n$相互独立，则$$ \mathbb{E} \bigg[\prod_{i=1}^n X_i\bigg] = \prod_{i=1}^n \mathbb{E} [X_i] $$且对于任意给定函数$f$，都有$f(X_1),f(X_2 ),...,f(X_n)$相互独立。反之不一定成立。不论随机变量
$X_1,X_2,...,X_n$是否独立，总有$$ \mathbb{E} \bigg[ \sum_{i=1}^n a_i X_i\bigg] = \sum_{x_1, ..., x_n} a_i x_i \Pr[X_i = x_i] = \sum_{i=1}^n a_i \mathbb{E}[X_i] $$
2 泊松分布与指数分布
-
泊松分布：将一个时间段切分成等大小的时间片，每个时间片内事件只有 “发生” 和“不发生”两种情形（每个时间片内是伯努利分布，多个时间片是二项分布），泊松分布的随机变量就是 该二项分布在时间片个数趋于无穷时事件发生的个数。
将该随机变量记为
$X$，事件发生的概率为$p$，则$P(X=k)=\lim_{n \to \infty} \tbinom{n}{k} p^k (1-p)^{1-k}$。因为二项分布的期望值$\mathbb{E}[X]=np$，不妨记为$\mu$，则$p = \frac{\mu}{n}$，带回上式可得即可得$$ P(X = k) = \lim_{n \to \infty} \frac{\mu^k}{k!} e^{-\mu} $$这就是泊松分布的概率密度函数。 -
指数分布：若某事件在给定时间段内发生的次数服从泊松分布，那么指数分布的随机变量就是 该事件前后两次发生的时间间隔。引入时间参数
$t$，令$\mu = \lambda t$，$t=1$表示整个时间段，$t=0.5$表示半个时间段，则$$ P(X = k) = P(X = k, t) = \lim_{n \to \infty} \frac{(\lambda t)^k}{k!} e^{-\lambda t} $$令随机变量$Y$是 两个事件发生的时间间隔，则$Y > t$的概率等价于$t$时间内事件发生$0$次的概率，即$$ P_Y (Y> t) = P_X (X = 0, t) = e^{-\lambda t} $$所以有$$ P_Y (Y \leq t) = 1 - e^{-\lambda t} $$这就是指数分布的概率密度函数。 -
无记忆性：指数分布（连续）和几何分布（离散）具有无记忆性。即
$$ P(X> s + t \mid X > s) = P(X > t) $$这意味着，事件发生的概率并不会伴随着等待的时间变长而增加，事件第$n+1$次发生与第 1 次发生概率一样，不会因为已经发生了$n$次而改变。这一结论与人类的本能 “赌徒心理” 正好相反。比特币基于 PoW 的共识机制正是利用了这种无记忆性。在任意时刻加入对 nonce 的猜测，都不会改变猜中的概率。这就给予了矿工们 “与算力成比例的” 优势。
3 使用概率论解决实际问题
3.1 问题 1
对应任意硬币（可能被做假，不妨假设正面落下的概率为 $p$，反面落下的概率为 $q$，$p+q=1$），试证明：通过如下方法总能产生公平的抛硬币效果，并求解 BiasedCoin() 的期望调用次数。
求解：若停机，则必然有 $x \neq y$，所以
$$ \Pr [x = 0 \wedge y = 1 \mid x \neq y] = \Pr [x = 1 \wedge y = 0 \mid x \neq y] = \frac{pq}{2 pq} = \frac{1}{2} $$
这里运用了 $x$ 和 $y$ 相互独立。
令随机变量 $T$ 为 BiasedCoin() 的调用次数，则
$$ \mathbb{E} [T] = \mathbb{E} [T \mid x \neq y] \cdot \Pr [x \neq y] + \mathbb{E} [T \mid x = y] \cdot \Pr [x = y] $$
其中，$\Pr [x \neq y] = 2 pq$，$\mathbb{E} [x \neq y] = 2$（因为一轮就结束了，只运行了两次）。此外有 $\Pr [x = y] = 1 - 2pq$，$\mathbb{E} [T \mid x = y] = 2 + \mathbb{E} [T]$（递归调用），联立可解得 $\mathbb{E} [T] = \frac{1}{pq}$。
3.2 问题 2
假设有 $n$ 种不同的卡，每次买一包干脆面可以抽出一种卡。假设买了 $n$ 包干脆面，可以抽出多少张不同的卡？为了收集到全部种类的卡，至少要买几包干脆面？
求解：对应第 $i$ 种卡，定义随机变量 $X_i \in \{0,1\}$ 表示我们是否拥有它。定义随机变量 $X$ 表示我们拥有的、不同种类的卡的个数。显然有 $X = \sum_{i} X_i$。
所以 $\mathbb{E} [X] = \sum_{i} \mathbb{E} [X_i] = \sum_{i} \mathbb{E} \Pr [X_i = 1]$。
在 $n$ 次购买中，$\forall i$，我们没有抽到第 $i$ 种卡的概率为 $\Pr [X_i = 0] = \big( 1 - \frac{1}{n} \big)^n \approx \frac{1}{e}$（这是因为每次购买抽出第 $i$ 种卡的概率服从独立同分布），所以 $\mathbb{E} [X] \approx \frac{n}{e} \approx 0.632 n$。
设 $T(n)$ 为收集了 $n$ 种卡所购买的干脆面的包数。将购买行为划分为 $n$ 个阶段，第 $i$ 个阶段在抽到第 $i$ 种卡之后停止。用 $T_i (n)$ 表示第 $i$ 个阶段购买的干脆面的包数。
则 $T(n)=\sum_{i=1}^n T_i (n)$。在第 $i$ 个阶段，抽到一张新卡的概率为 $\frac{n - (i-1)}{n}$，此时 $T_i (n)$ 实际上是一个几何分布的随机变量，根据几何分布的期望可知 $\mathbb{E} [T_i (n)] = \frac{n}{n-i+1}$，所以
$$ \mathbb{E} [T(n)] = \sum_{j=1}^n \frac{n}{j} = n (1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}) $$
后面这个几何级数满足 $\ln (n + 1) \leq \sum_{j=1}^n \frac{1}{j} \leq \ln n + 1$（借助每段函数 $\frac{1}{j}$ 的上下界函数的积分来计算），所以可得结论：至少要买 $\Theta (n \ln n)$ 包。
转载申请
本作品采用 知识共享署名 4.0 国际许可协议 进行许可，转载时请注明原文链接。您必须给出适当的署名，并标明是否对本文作了修改。