01 离散概率

The true logic of this world is in the calculus of probabilities. ——James Clerk Maxwell

我们平时在生活中经常使用“概率”、“机会”或“可能性”这样的词，通常我们是在做一种猜测或做一种预判。为什么我们要猜测呢？因为我们希望在不完全掌握所有信息时做出我们必须做出的决定。我们在生活中所使用的“概率”一词，指的通常是在大量重复某个观察时，用一个0到1之间的数来概括其出现的可能性。例如当我们重复了100000次抛硬币的实验，观察到有50000次实验中正面朝上，我们就说正面朝上的概率是$1/2$。我们只能对“可重复”的观察谈概率。概率是观察者所做出的“统计结果”，而不是事物本身的属性。概率有赖于我们的知识以及进行估计的能力。很有可能，当我们所掌握的知识发生变化后，对事物的概率的估计就会变得完全不同。

离散概率空间

“概率是大量观察以后用一个数来估计可能性”，这样的定义显然不是一种严格的数学定义。如果要想这样定义，必须先严格定义什么是“估计”，什么是“可能性”，什么是“大量观察”。所以，在“概率论”中，我们首先要从数学的观点来定义概率，然后再去看这样的定义满足什么性质，这样的性质是否与人们常识中所认识的概率相符。而这里说的“数学的观点”，就是基于集合论的语言来定义概念，描述性质。

本文所涉及的都是离散概率， 我们会在下一篇文章开始再讨论更复杂的概率。也就是说，我们不会讨论“在$[0,1]$实数区间里随机选一个线段”这样的情况，而只讨论“抛一个立方体骰子”“抛$n$次硬币”这样的“有限”的情况。我们会看到，离散概率所涉及的数学本质上来说只是一些组合计数，并不会涉及高深的分析学理论。

让我们从掷骰子的例子出发，来引入描述概率的数学语言。当我们反复完成“掷骰子”的动作时，由于每次动作都会有细微的不同，得到的点数可能各不相同。重复许多次这个动作以后，我们发现点数$1,2,3,4,5,6$出现的次数大约都各占总数的$1/6$。于是我们说“掷出$6$”的概率是$1/6$。我们还可以进一步推理出，“掷出的点数大于等于$3$”的概率是$1/2$。在这里，我们涉及到了三个关键点：骰子产生的结果是$1,2,3,4,5,6$中的恰好一个数字；诸如“掷出$6$”或“掷出的点数大于等于$3$”这样的表达都可以有一个概率与其对应；概率是一个$0$到$1$之间的实数。

以上三点就构成了描述概率的三个基本组件：

• 我们把掷骰子可能产生的结果的集合称为样本集(sample set)，记为$\Omega$，在这里$\Omega=\{1,2,3,4,5,6\}$（在离散概率中，我们总是考虑有限的样本集）；
• “掷出$6$”或“掷出的点数大于等于$3$”这样的描述称为一个“事件(event)”，一个事件是样本集的一个子集，例如“掷出6”对应$\{6\}$，“掷出的点数大于等于$3$”对应$\{4,5,6\}$。由于我们假定了$\Omega$是有限集，那么我们可以定义事件集(set of event)为样本集的幂集，记为$\mathcal{F}=2^\Omega$。事件是事件集的元素；
• 事件集中的每个事件对应$[0,1]$中一个实数。这就称为事件的概率，它是一个$\mathcal{F}\to [0,1]$的函数，记为$P$。在掷骰子的例子中，由单个样本所构成的事件集的概率都为$1/6$，而多个元素的事件集的概率等于这些元素的单元集的概率之和，例如设$A=\{4,5,6\} \in \mathcal{F}$，有$P(A)=1/2$。全集是一个事件，它的概率应当为1；空集也是一个事件，它的概率应当为0；如果$A$的概率为$p$，那么$A$的补集的概率应当为$1-p$；

基于上述观察，我们下面严格定义“离散概率空间”的概念：

离散概率空间(discrete probability space)是一个三元组$(\Omega,\mathcal{F},P)$。其中$\Omega$是一个有限集合，称为样本集。$\mathcal{F}=2^\Omega$，称为事件集；$P:\mathcal{F}\to [0,1]$称为概率函数。概率函数要满足下面三个条件：

• $P(\varnothing)=0,P(\Omega)=1$
• $\forall A\in \mathcal{F}, P(A)+P(\Omega \setminus A)=1$
• 对于两两无交的事件序列$A_1,A_2,\cdots,A_n$，$P\left(\bigcup\limits_{i =1}^{n}A_i\right)=\sum\limits_{i=1}^{n}P(A_i)$

Rmk. 事件是集合，因此我们可以用集合的符号来表示来表示事件的发生：例如$A \cup B$表示“事件$A$或事件$B$发生”，$A \cap B$表示“事件$A$与事件$B$同时发生”。我们还可以记$\overline{A}=\Omega \setminus A$，表示“事件$A$不发生”

在离散概率中，$\Omega$中的每一个元素自身构成的单元集是一个事件，称为“基本事件(basic event)”。概率函数的条件三意味着，只要确定每个基本事件的概率，原则上就可以求出任何事件的概率。

条件概率与独立事件

条件概率的定义

在掷骰子的例子中，我们之所以认为基本事件的概率是$1/6$，是因为在掷骰子之前我们没有任何理由倾向于某个特定的结果。这就好像，如果把你关在一个房间里，由你的朋友在隔壁房间掷骰子，接着你的朋友让你来猜骰子的结果，这时候的你因为不掌握任何特殊信息，所以只能随便猜一个结果，你猜对的概率就是$1/6$。可是，如果你的朋友在让你猜之前，透露给你说“骰子的结果是一个偶数哦~”，这时候你只会在2，4，6这三个选项里猜，所以你猜对的概率变成了$1/3$。如果你的朋友透露给你说“骰子的结果大于4”，那么你猜对的概率就能达到$1/2$。

上面的例子说明，如果我们掌握了一些信息，那么就可以从样本集里排除一些样本，事件的概率就会变成这个“子概率空间”中的概率。同时，“掌握的信息”也可以用一个事件来描述。比如，朋友告诉你“骰子的结果是偶数”，这本身对应一个事件$\{2,4,6\}$。所以，新的概率是把“已知某一事件发生”作为条件时的概率，我们把这样的概率称为“条件概率(conditional probability)”。它的计算方法应当是用“已知事件发生的概率”作为分母“两事件同时发生的概率”作为分子所得的分数：

对于概率空间$(\Omega,\mathcal{F},P)$中的两个事件$A,B \in\mathcal{F}$，定义$A$事件在$B$事件发生下的条件概率为

$$P(A\mid B)=\dfrac{P(A \cap B)}{P(B)}$$

例如，“掷出$6$”在“掷出偶数”发生下的条件概率为$P(\{6\}\mid \{2,4,6\})=$ $\dfrac{P(\{6\})}{P(\{2,4,6\})}=\dfrac{1/6}{1/2}=\dfrac{1}{3}$。

独立事件的定义

考虑“连续抛两次硬币”的过程，为了描述这一过程的可能结果，可以这样建立样本空间：$\Omega=\{(x,y)\mid x,y\in \{0,1\}\}$，每个样本是两次抛硬币结果的有序对，正面为1，反面为0。事件集是$2^\Omega$，每个基本事件的概率都是相等的，也就是$1/4$。对于“连续抛两次硬币”这一过程，我们有这样一个常识：“第一次抛出正面”和“第二次抛出正面”这两个事件应当是“毫无关系”的，并不会因为第一次抛出了正面而改变第二次抛出正面的概率。这一常识可以用条件概率来描述，如果对于事件$A,B\in \mathcal{F}$，如果$P(B)=P(B\mid A)$，并且$P(A)=P(A\mid B)$，就说明$A,B$这两个事件是“毫无关系”的。根据条件概率的定义，$P(B)=P(B\mid A)$与$P(A)=P(A\mid B)$这两个式子是等价的，它们都等价于$P(A)\cdot P(B)=P(A\cap B)$。

我们就把这一特性作为事件的独立性的定义：在概率空间$(\Omega,\mathcal{F},P)$中，两个事件$A,B \in\mathcal{F}$是独立的(independent)当且仅当：

$$P(A \cap B)=P(A) \cdot P(B)$$

对于有限多个事件$A_1,\cdots,A_n$，定义它们“两两独立(pairwise independent)”当且仅当$\forall i,j\in [n]$，$P(A_i\cap A_j)=P(A_i)P(A_j)$，定义它们“互相独立(mutually independent)”当且仅当对于任何$I\subseteq [n]$，$P(\bigcap\limits_{i \in I}A_i) = \prod\limits_{i \in I}P(A_i)$。

Rmk. “互相独立”的要求比“两两独立”的要求更高。显然，互相独立一定意味着两两独立。下面我们来举一个两两独立但不互相独立的例子。还是考虑上面的“抛两次硬币”的例子。设事件$A_1$是“两次结果相同”，$A_2$是“第一次抛出正面”，$A_3$是“第二次抛出正面”。那么$P(A_1)=1/2$，$P(A_2)=1/2$，$P(A_3)=1/2$，$P(A_1\cap A_2\cap A_3)=P(\{(1,1)\})=1/4$ $\neq P(A_1)P(A_2)P(A_3)$，所以$A_1,A_2,A_3$不是互相独立的。但是$P(A_1\cap A_2)=1/4$，$P(A_1\cap A_3)=1/4$，$P(A_2\cap A_3)=1/4$，因此$A_1,A_2,A_3$是互相独立的。

应当意识到，并不是对于所有的独立事件我们都能在脑海中建立起直观的印象。例如在掷一次骰子的例子中，“掷出$1$或$2$”与“掷出$1$或$3$或$4$”发生的概率分别为$1/3$和$1/2$，它们同时发生也即“掷出$1$”发生的概率恰好为$1/6$。所以根据定义，“掷出$1$或$2$”与“掷出$1$或$3$或$4$”这两件事是独立的。但是这个“独立”如何在直观上解释呢？其实我们并无法给出一个特别好的解释，这更像是某种数值上的巧合。在应用中，更多的是反过来——我们已经意识到某两个事件在直观上应当是独立的了（例如先后两次的抛硬币的过程），然后按照独立的定义去验证确实如此。

链式法则

我们可以把条件概率的等式变形为$P(A\cap B) = P(A\mid B) \cdot P(B)$。于是我们能够得到一个求解事件的交集的概率的链式法则(chain rule)：

$$\begin{aligned} &P(A_1 \cap \cdots \cap A_n)\\ =&P(A_n\mid A_1 \cap \cdots \cap A_{n-1}) \cdot P(A_1 \cap \cdots \cap A_{n-1})\\ =&\cdots \\ =&P(A_n\mid A_1 \cap \cdots \cap A_{n-1})\cdot P(A_{n-1}\mid A_1 \cap \cdots \cap A_{n-2}) \cdots\\&P(A_3\mid A_1 \cap A_2)\cdot P(A_2 \mid A_1)\cdot P(A_1) \end{aligned}$$

全概率公式

对于$A,B \in \mathcal{F}$，可以证明$P(A)=P(A \cap B)+P(A \cap \overline{B})$：因为$B$与$\overline B$是互不相交的，因此$A\cap B$与$A\cap \bar B$也互不相交，那么根据概率函数的条件三有$P(A\cap B)+P(A\cap \bar B)=P((A\cap B)\cup (A\cap \bar B))=P(A)$。

在上一段中，$B,\overline{B}$构成了全集$\Omega$的一个partition。我们可以把以上结论推广到$n$个事件构成的partition上：如果$\Omega$有partition $B_1, \cdots ,B_n$，那么$\forall A\in \mathcal{F}$，有：

$$P(A)=\sum\limits_{i=1}^{n}P(A \cap B_i)$$

这称为全概率公式(law of total probability)

随机变量

我们再来考虑“掷两个骰子”的例子。当我们问“两次掷骰子的点数之和是多少？”这个问题时，问题的答案不是一个确定的数字，而应该是一系列可能的数字。点数之和最小可能是$2$，如果两次都掷出了$1$，但这只有$1/36$的概率会发生。相比之下，点数之和是$6$的概率达到$5/36$，因为$(1,5),(2,4),(3,3),(4,2),(5,1)$都会产生这一结果。所以，这个问题的答案应该是一个“分布”：$1/36$的概率答案为$2$，$2/36$的概率答案为$3$，$3/36$的概率答案为$4$，$4/36$的概率答案为$5$，$5/36$的概率答案为$6$，$6/36$的概率答案为$7$，$5/36$的概率答案为$8$，$4/36$的概率答案为$9$，$3/36$的概率答案为$10$，$2/36$的概率答案为$11$，$1/36$的概率答案为$12$。

随机变量的定义

为了更好的描述这个问题，我们可以建立一个从样本空间到实数的函数$X:\Omega \to \R$。在“点数之和”的例子里，我们可以令$X((x,y))=x+y$。例如，$(2,5)$这个样本会被$X$映射到实数$7$。基于一些历史的原因，这样的函数称为随机变量(random variables)。在离散概率中，任何$\Omega \to \R$的函数都可以作为一个随机变量。

对于随机变量$X:\Omega \to \R$，我们用符号“$X=a$”来表示“随机变量$X$的取值为$a$”这一事件，也即集合$\{s\in \Omega\mid X(s)=a\}$，也即函数$X$在$a$上的原像$X^{-1}(a)$。对于离散概率空间，这一集合要么存在要么为空。更一般的，对于$\R$的子集$A$也可以定义事件“$X \in I$”，它对应集合$X^{-1}(I)$，也即$\{s \in \Omega\mid X(s) \in I\}$。

我们特别地定义一个记号$\mathbb{1}[A]$（其中$A$是一个事件），它是一个随机变量，称为事件$A$的indicator。它满足：$\mathbb1 [A](\omega)=1$当且仅当$\omega \in A$，否则$\mathbb{1}[A](\omega)=0$。它用来“指示(indicate)”事件$A$发生与否。

我们可以枚举基本事件来计算$P(X=a)$：

$$P(X=a)=\sum\limits_{X(s)=a,s\in\Omega}P(s)$$

对于离散概率，可以定义两个随机变量$X,Y$的“和”：$(X+Y)(\omega)=X(\omega)+Y(\omega)$。它依然是一个随机变量。同理，也可以定义随机变量的乘积、商等等。

随机变量的分布

对于随机变量，我们通常最关心的就是当$a$取各个不同值得时候$P(X=a)$的大小，这称为随机变量的分布(distribution)。对于离散的随机变量，我们可以定义一个$\R\to [0,1]$的函数$p$来描述分布，其中

$$p(a):=P(X=a)$$

$p$称为概率质量函数(probability mass function)。

因为样本空间是有限的，所以$p$只会在有限个点上有值，其余地方值都为$0$。显然，有$\sum\limits_{a\in \R}p(a)=1$。

随机变量的独立性

“随机变量等于某个值”是一个事件，我们可以把关于事件性质的描述方法迁移到随机变量上。

对于随机变量$X,Y$，称$X$与$Y$是独立的，当且仅当对于任意的$a,b\in \R$成立$P((X=a)\cap (Y=b))=P(X=a)\cdot P(Y=b)$，记为$X \perp Y$。

如果有限多个随机变量两两之间是独立的，就称这列随机变量两两独立(pairwise independent)。

称有限多个随机变量$X_1,\cdots,X_n$是“互相独立(mutually independent)”的，当且仅当对于$\forall a_1,\cdots,a_n\in\R,\forall I\subseteq [n]$，$P[\bigcap\limits_{i \in I}(X_i=a_i)] =$ $\prod\limits_{i \in I}P(X_i=a_i)$。

随机变量的期望

期望(expectation)是随机变量的一个重要特征，它用来描述随机变量的“平均值”。在离散概率空间中，定义：

$$\mathbb{E}[X] :=\sum\limits_{a\in \R}a\cdot P(X=a)$$

它也可以按照基本事件来给出：

$$\mathbb{E}[X]=\sum\limits_{\omega \in \Omega}X(\omega)P(\omega)$$

容易证明这二者是等价的。

关于期望，一个最重要的事实称为“期望的线性性(linearity)”。它指出有限个随机变量的和（依然是一个随机变量）的期望总是等于这些随机变量的期望的和。对于有限个随机变量$X_1,\cdots,X_n$，始终满足：

$$\mathbb{E}\left[\sum\limits_{i=1}^{n}X_i\right]=\sum\limits_{i=1}^{n}\mathbb{E}[X_i]$$

我们对于两个随机变量的情况给出证明：$\mathbb{E}[X+Y]=\sum\limits_{\omega\in \Omega}(X(\omega)+Y(\omega))P(\omega)=$ $\sum\limits_{\omega\in \Omega}X(\omega)P(\omega)+$ $\sum\limits_{\omega\in \Omega}Y(\omega)P(\omega)$ $=\mathbb{E}[X]+\mathbb{E}[Y]$，证毕。期望的线性性重要在于，它没有对随机变量提出任何的要求，即使两个随机变量不是“独立”的，也有期望的线性性。“期望的线性性”是“期望”的性质，不是“随机变量”的性质。期望的线性性会在我们计算时提供极大的方便。

Rmk. 从更高的角度看，期望的线性性其实来自于“加权求和”这一运算的线性性。这个性质在连续世界里就是“积分的线性性”。在离散概率中，期望的线性性可以看作积分线性性的离散表达。

当然，为了完善“线性性”这一概念，我们还应当证明

$$\forall c\in \R,\mathbb{E}[cX]=c\mathbb{E}[X]$$

这是容易的，$\mathbb{E}[cX]=\sum\limits_{\omega\in \Omega}cX(\omega)P(\omega)=c\sum\limits_{\omega\in \Omega}X(\omega)P(\omega)=c\mathbb{E}[X]$。

Rmk. 必须要指出的是，期望的线性性只对“有限个变量”成立。当变量有无穷个时，它是不正确的。从连续世界的视角看，当变量有无穷个时“变量之和”是一个极限过程，期望本身是一个积分因此也是一个极限过程，因此期望的线性性就是一个“极限符号能否交换位置的问题”（重积分能否化为累次积分的问题），我们知道这是需要额外条件的。

条件期望

我们可以仿照条件概率，定义条件期望(conditional expectation)。对于随机变量$X$和事件$A\in\mathcal{F}$：

$$\mathbb{E}[X\mid A]:=\sum\limits_{a\in \R}a\cdot P(X=a\mid A)$$

这等价于

$$\mathbb{E}[X\mid A]=\sum\limits_{\omega}X(\omega)\cdot P(\omega\mid A)$$

条件期望表示“在事件$A$发生的条件下”随机变量$X$的期望。例如，如果随机变量$X$表示掷骰子所得的点数，那么$\mathbb{E}[X]=3.5$。而当事件$A$为“骰子点数为偶数”时，$\mathbb{E}[X\mid A]=4$，因为在事件$A$作为前提时$X$取奇数的概率为0，所以$1,3,5$不会在统计平均数时被计入在内。

仿照全概率公式$P(B)=\sum\limits_{i=1}^{n}P(B \cap A_i)$，我们有：

$$\mathbb{E}[X]=\sum\limits_{i=1}^{n}E[X\mid A_i]\cdot P(A_i)$$

证明：$\mathbb{E}[X]=\sum\limits_{a}a\cdot P(X=a)=\sum\limits_{a}a\cdot \sum\limits_{i\in [n]}P(X=a\cap A_i)=\sum\limits_{a}a\cdot \sum\limits_{i\in [n]}P(A_i)P(X=a\mid A_i)$ $=\sum\limits_{i\in [n]}P(A_i)\sum\limits_{a}a\cdot P(X=a\mid A_i)=\sum\limits_{i\in [n]}P(A_i)\mathbb{E}[X\mid A_i]$。不妨把这称为“全期望公式”。

几类特殊的离散分布

伯努利分布

设$p\in[0,1]$是一个常数。如果随机变量$X$满足$P[X=1]=p,P[X=0]=1-p$，那么称$X$为伯努利(Bernoulli)随机变量，记为$X\sim \text{Ber}(p)$。$X$的分布称为伯努利分布。例如，抛硬币的结果就是一个伯努利分布$X\sim\text{Ber}(1/2)$。

对于伯努利分布$X\sim \text{Ber}(p)$，$\mathbb{E}[X]=1\cdot p+0\cdot (1-p)=p$。

二项分布

把伯努利变量$X\sim \text{Ber}(p)$独立重复$n$次，第$i$次的随机变量记为$X_i$，那么$Y=\sum\limits_{i=1}^{n}X_i$就称为一个二项(binomial)随机变量。它满足二项分布：$P(Y=k)=\dbinom{n}{k}p^k(1-p)^{n-k}$。

二项随机变量的期望$\mathbb{E}[Y]=\mathbb{E}\left[\sum\limits_{i=1}^{n}X_i\right]$，根据期望的线性性，$\mathbb{E}\left[\sum\limits_{i=1}^{n}X_i\right]=\sum\limits_{i=1}^{n}\mathbb{E}[X_i]=\sum\limits_{i=1}^{n}p=np$。

几何分布

如果把二项分布理解为抛$n$次硬币统计正面朝上的次数，那么几何(geometric)分布就可以理解为不停抛硬币直到第一次出现正面所需要的次数。设$X\sim \text{Ber}(p)$，如果$Z$满足几何分布，那么$P(Z=n)=(1-p)^{n-1}p$。

如何计算几何分布的期望？从直觉上看，丢一个$1/10$概率出正面的硬币大约需要10次，因此我们可以猜测$\mathbb{E}[X]=\dfrac{1}{p}$。事实确实如此，按照定义计算即可验证。

参考资料

[1] Chihao Zhang, SJTU Combinatorics in Computer Science (Spring 2023)
[2] Michael Mitzenmacher, Eli Upfal, Probability and Computing