概率 & 期望
样本空间、随机事件
定义
一个随机现象中可能发生的不能再细分的结果被称为 样本点。所有样本点的集合称为 样本空间，通常用 \(\Omega\) 来表示。
一个 随机事件 是样本空间 \(\Omega\) 的子集，它由若干样本点构成，用大写字母 \(A, B, C, \cdots\) 表示。
对于一个随机现象的结果 \(\omega\) 和一个随机事件 \(A\)，我们称事件 \(A\) 发生了 当且仅当 \(\omega \in A\)。
例如，掷一次骰子得到的点数是一个随机现象，其样本空间可以表示为 \(\Omega=\{1,2,3,4,5,6\}\)。设随机事件 \(A\) 为「获得的点数大于 \(4\)」，则 \(A = \{ 5, 6 \}\)。若某次掷骰子得到的点数 \(\omega = 3\)，由于 \(\omega \notin A\)，故事件 \(A\) 没有发生。
事件的运算
由于我们将随机事件定义为了样本空间 \(\Omega\) 的子集，故我们可以将集合的运算（如和、差、交、并、补等）移植到随机事件上。记号与集合运算保持一致。
特别的，事件的并 \(A \cup B\) 也可记作 \(A + B\)，事件的交 \(A \cap B\) 也可记作 \(AB\)，此时也可分别称作 和事件 和 积事件。
因为事件在一定程度上是以集合的含义定义的，因此可以把事件当作集合来对待。
和事件 ：相当于 并集 。若干个事件中只要其中之一发生，就算发生了它们的和事件。
积事件 ：相当于 交集 。若干个事件必须全部发生，才算发生了它们的积事件。
概率
定义
古典定义
在概率论早期实践中，由于涉及到的随机现象都比较简单，具体表现为样本空间 \(\Omega\) 是有限集，且直观上所有样本点是等可能出现的，因此人们便总结出了下述定义：
如果一个随机现象满足：
- 只有有限个基本结果；
- 每个基本结果出现的可能性是一样的；
那么对于每个事件 \(A\)，定义它的概率为
\[P(A)=\frac{card(A)}{card(\Omega)} \]其中 \(card()\) 表示对随机事件（一个集合）大小的度量。
统计定义
如果在一定条件下，进行了 \(n\) 次试验，事件 \(A\) 发生了 \(N(A)\) 次，如果随着 \(n\) 逐渐增大，频率 \(\displaystyle\frac{N_A}{N}\) 逐渐稳定在某一数值 \(p\) 附近，那么数值 \(p\) 称为事件 \(A\) 在该条件下发生的概率，记做 \(P(A)=p\)。
公理化定义
概率函数 \(P\) 是一个从事件域 \(\mathcal{F}\) 到闭区间 \([0, 1]\) 的映射，且满足：
- 规范性：事件 \(\Omega\) 的概率值为 \(1\)，即 \(P(\Omega)=1\)。
- 可数可加性：若一列事件 \(A_1, A_2, \cdots\) 两两不交，则 \(\displaystyle P\left( \bigcup_{i \geq 1} A_i \right) = \sum_{i \geq 1} P(A_i)\)。
概率函数的性质
对于任意随机事件 \(A, B \in \mathcal{F}\)，有
- 单调性：若 \(A \subset B\)，则有 \(P(A) \leq P(B)\)。
- 容斥原理：\(P(A+B) = P(A) + P(B) - P(AB)\)。
- \(P(A - B) = P(A) - P(AB)\)，这里 \(A - B\) 表示差集。
条件概率
定义
若已知事件 \(A\) 发生，在此条件下事件 \(B\) 发生的概率称为 条件概率，记作 \(P(B|A)\)。
在概率空间 \((\Omega, \mathcal{F}, P)\) 中，若事件 \(A \in \mathcal{F}\) 满足 \(P(A) > 0\)，则条件概率 \(P(B|A)\) 定义为
\[P(B|A) = \frac{P(AB)}{P(A)} \qquad \forall B \in \mathcal{F} \]可以验证根据上式定义出的 \(P(B|A)\) 是 \((\Omega, \mathcal{F})\) 上的概率函数。
根据条件概率的定义可以直接推出下面两个等式：
- 概率乘法公式：在概率空间 \((\Omega, \mathcal{F}, P)\) 中，若 \(P(A) > 0\)，则对任意事件 \(B\) 都有
- 全概率公式：在概率空间 \((\Omega, \mathcal{F}, P)\) 中，若一组事件 \(A_1, \cdots, A_n\) 两两不交且和为 \(\Omega\)，则对任意事件 \(B\) 都有
Bayes 公式
一般来说，设可能导致事件 \(B\) 发生的原因为 \(A_1, A_2, \cdots, A_n\)，则在 \(P(A_i)\) 和 \(P(B|A_i)\) 已知时可以通过全概率公式计算事件 \(B\) 发生的概率。但在很多情况下，我们需要根据「事件 \(B\) 发生」这一结果反推其各个原因事件的发生概率。于是有
\[P(A_i|B) = \frac{P(A_iB)}{P(B)} = \frac{P(A_i)P(B|A_i)}{\displaystyle\sum_{j=1}^{n} P(A_j)P(B|A_j)} \]上式即 Bayes 公式。
事件的独立性
在研究条件概率的过程中，可能会出现 \(P(B|A) = P(B)\) 的情况。从直观上讲就是事件 \(B\) 是否发生并不会告诉我们关于事件 \(A\) 的任何信息，即事件 \(B\) 与事件 \(A\)「无关」。于是我们就有了下面的定义
定义
若同一概率空间中的事件 \(A\)，\(B\) 满足
\[P(AB) = P(A)P(B) \]则称 \(A\)，\(B\) 独立。对于多个事件 \(A_1, A_2, \cdots, A_n\)，我们称其独立，当且仅当对任意一组事件 \(\{ A_{i_k} : 1 \leq i_1 < i_2 < \cdots < i_k \leq n \}\) 都有
\[P( A_{i_1}A_{i_2} \cdots A_{i_r} ) = \prod_{k=1}^{r} P(A_{i_k}) \]直观地说，我们认为两个东西独立，当它们在某种意义上互不影响。例如，一个人出生的年月日和他的性别，这两件事是独立的；但一个人出生的年月日和他现在的头发总量，这两件事就不是独立的，因为一个人往往年纪越大头发越少。数学中的独立性与这种直观理解大体相似，但不尽相同。
多个事件的独立性
对于多个事件，一般不能从两两独立推出这些事件独立。考虑以下反例：
有一个正四面体骰子，其中三面被分别涂成红色、绿色、蓝色，另一面则三色皆有。现在扔一次该骰子，令事件 \(A\),\(B\),\(C\) 分别表示与桌面接触的一面包含红色、绿色、蓝色。
不难计算 \(P(A) = P(B) = P(C) = \displaystyle\frac{1}{2}\)，而 \(P(AB) = P(BC) = P(CA) = P(ABC) = \displaystyle\frac{1}{4}\)。
显然 \(A\)，\(B\)，\(C\) 两两独立，但由于 \(P(ABC) \ne P(A)P(B)P(C)\)，故 \(A, B, C\) 不独立。
随机事件的独立性
我们称两个事件 \(A\)，\(B\) 独立，当 \(P(A \cap B) = P(A) \cdot P(B)\)。
我们称若干个事件 \(A_{1,\dots,n}\) 互相独立，当对于其中的任何一个子集，该子集中的事件同时发生的概率，等于其中每个事件发生的概率的乘积。形式化地说：
\[P(\bigcap_{E \in T} E) = \prod_{E \in T} P(E). \forall T \subseteq \{A_1,A_2,\dots,A_n\} \]由此可见，若干事件 两两独立 和 互相独立 是不同的概念。
随机变量的独立性
一下用 \(I(X)\) 表示随机变量 \(X\) 的取值范围。即，如果把 \(X\) 看做一个映射，则 \(I(X)\) 看做它的值域。
我们称两个随机变量 \(X,Y\) 独立，当 \(P((X = \alpha) \cap (Y = \beta)) = P(X = \alpha) P(Y = \beta)\), \(\forall\alpha\in I(X),\beta\in I(Y)\)，即 \((X,Y)\) 取任意一组值得概率，等于 \(X\) 和 \(Y\) 分别取对应值得概率的乘积。
我们称若干个随机变量 \(X_{1,\dots,n}\) 互相独立，当 \((X_1,X_2,\dots,X_n)\) 取任意一组值得概率，等于每个 \(X_i\) 分别取对应值的概率的乘积。形式化地说：
\[P\Big(\bigcap_{i = 1}^n X_i = F_i\Big) = \prod_{i = 1}^{n} P(X_i = F_i), \forall F_{1,\dots,n} s.t. F_i \in I(X_i) \]由此可见，若干随机变量 两两独立 和 互相独立 是不同的概念。
概率的计算
-
广义加法公式：对于任意两个事件 \(A,B\) 有 \(\displaystyle P(A \cup B) = P(A) + P(B) - P(A \cap B)\)。
-
条件概率：记 \(P(B \mid A)\) 表示在 \(A\) 事件发生的前提下， \(B\) 事件发生的概率。则 \(\displaystyle P(B \mid A) = \frac{P(AB)}{P(A)}\)，其中 \(P(AB)\) 为事件 \(A\) 和事件 \(B\) 同时发生的概率。
-
乘法公式：\(P(AB) = P(A) \cdot P(B \mid A) = P(B) \cdot P(A \mid B)\)。
-
全概率公式：若事件 \(A_1,A_2,A_3.\dots,A_n\) 构成一组完备的事件且都有正概率，即 $\forall i,j,A_i \cap A_j = \varnothing $ 且 \(\displaystyle \sum_{i = 1}^n A_i = 1\)， 则有 \(\displaystyle P(B) = \sum_{i=1} ^nP(A_i)P(B \mid A_i)\)。
-
贝叶斯定理：\(\displaystyle P(B_i \mid A) = \frac{P(B_i) P(A \mid B_i)}{\displaystyle \sum_{j = 1}^n P(B_j) P(A \mid B_j)}\)
随机变量
直观地说，一个随机变量，是一个取值由随机事件决定的变量。
如果基于概率的公理化定义，那么一个随机变量。形式化地说——是一个从样本空间 \(S\) 到实数集 \(\R\)（或者 \(\R\) 的某个子集）的映射 \(X\) 。如果 \(X(A) = \alpha\)，你可以直观理解为：当随机实验 \(E\) 取结果 \(A\) 时，该随机变量取值 \(\alpha\)。
由此可以看到，“随机变量 \(X\) 取值 \(\alpha\) ”（简记为 \(X = \alpha\)）也对应着一个能实现该命题的单位事件集合，因此它也是一个事件，于是也有与之对应的概率 \(P(X = \alpha)\)。
期望
引入
想象一下这样一个场景：狗狗 Emissary 想找 tsqtsqtsq 打 slay，但是 tsqtsqtsq 今天想搞卷，于是他想出了这样个办法：
- 如果狗狗 Emissary 在今天的 \(\texttt{clg round}\) 中获得大于 300 pts，tsqtsqtsq 就会陪它打三小时。
- 如果狗狗 Emissary 在今天的 \(\texttt{clg round}\) 中获得大于 200 pts，tsqtsqtsq 就会陪它打两小时。
- 如果狗狗 Emissary 在今天的 \(\texttt{clg round}\) 中获得大于 100 pts，tsqtsqtsq 就会陪它打一小时。
- 如果狗狗 Emissary 在今天的 \(\texttt{clg round}\) 中获得大于 0 pts，tsqtsqtsq 就会陪它打半小时。
因为狗狗 Emissary 很强，所以它不会保龄。
试求 tsqtsqtsq 陪狗狗 Emissary 打 slay 的期望时长。
我们首先根据条件列出下面这张表格：
| 分数 | 时长 | 概率 |
|---|---|---|
| \((300,400]\) | \(3\) 小时 | \(\displaystyle\frac{1}{4}\) |
| \((200,300]\) | \(2\) 小时 | \(\displaystyle\frac{1}{4}\) |
| \((100,200]\) | \(1\) 小时 | \(\displaystyle\frac{1}{4}\) |
| \((0,100]\) | \(0.5\) 小时 | \(\displaystyle\frac{1}{4}\) |
令狗狗 Emissary 在今天的 \(\texttt{clg round}\) 中获得大于 300 pts为事件 \(A\)。以此类推，其余三种事件分别为 \(B\)，\(C\)，\(D\)，不难求出期望时长为：
\[\displaystyle E(X)=\frac{1}{4}\times 3+\frac{1}{4}\times 2+\frac{1}{4}\times 1+\frac{1}{4}\times 0.5=\frac{13}{8}=1.625 \]所以 tsqtsqtsq 陪狗狗 Emissary 打 slay 的期望时长为 \(1.625\) 小时，即 \(97.5\) 分钟。
大数定律表明，随着重复次数接近无穷大，数值的算术平均值几乎肯定地收敛于期望值，即令第 \(i\) 次 \(\texttt{clg round}\) 后 tsqtsqtsq 陪狗狗 Emissary 打 slay 的时长为 \(f_i\)，总共有 \(x\) 次 \(\texttt{clg round}\)，则有：
\[\lim_{x\rightarrow\infty}\frac{\displaystyle\sum_{i=1}^{x}f_i}{x}=E(X) \]所以在打了不知道多少场 \(\texttt{clg round}\) 之后 tsqtsqtsq 陪狗狗 Emissary 打 slay 的时长肯定会趋近于这个期望时长。
定义
如果一个随机变量的取值个数有限（比如一个表示骰子示数的随机变量），或可能的取值可以一一列举出来（比如取值范围为全体正整数），则它称为 离散型随机变量 。
形式化地说，一个随机变量被称为离散型随机变量，当它的值域大小 有限 或者为 可列无穷大 。
一个离散性随机变量 \(X\) 的 数学期望 是其每个取值乘以该取值对应概率的总和，记为 $E(X) $。
\[E(X) = \sum_{\alpha \in I(X)} \alpha \cdot P(X = \alpha) = \sum_{\omega \in S} X(\omega) \cdot Y(\omega) \]其中 \(I(X)\) 表示随机变量 \(X\) 的值域，\(S\) 表示 \(X\) 所在概率空间的样本集合。
性质
- 全期望公式： \(\displaystyle E(Y)=\sum_{\alpha\in I(X)}P(X=\alpha)\cdot E(Y\mid(X=\alpha))\)，其中 \(X,Y\) 是随机变量，\(E(Y\mid A)\) 是在 \(A\) 条件成立下 \(Y\) 的期望（即“条件期望”）。可由全概率公式证明。
- 期望的线性性 ：对于任意两个随机变量 \(X\)，\(Y\) （不要求相互独立），有 \(E(\lambda X+\mu Y) = \lambda E(X) + \mu E(Y)\) 。利用这个性质，可以将一个变量拆分成若干个互相独立的变量，分别求这些变量的期望值，最后相加得到所求变量的值。
- 乘积的期望 : 当两个随机变量 \(X\)，\(Y\) 相互独立时，有 \(E(XY) = E(X) \cdot E(Y)\) 。
期望与概率的转化
对于随机事件 \(A\)，考虑其示性函数 \(I_A\)：
\[I_A(\omega) = \begin{cases} 1, & \omega \in A \\ 0, & \omega \notin A \end{cases} \]根据定义可以求得其期望 \(EI_A = P(A)\)。这一转化在实际应用中非常常见。
条件分布与条件期望
我们之前研究过条件概率，类似的也可以提出所谓条件期望的概念。
定义
对于两个随机变量 \(X\),\(Y\)，在已知 \(Y = y\) 的条件下 \(X\) 的概率分布（密度函数）称之为 条件概率分布（条件概率密度），分别记作
\[P( X = x_i | Y = y ) \qquad f_{X|Y}(x|y) \]在此条件下，\(X\) 的期望称为 条件期望，记作 \(E[X|Y=y]\)。
条件期望的性质
条件期望的诸多性质可由条件概率推知，在此不做赘述。
值得一提的是 \(E[X | Y]\) 一般是随机变量 \(Y\) 的函数，且这个函数通常不是线性的。但实际上有
\[E[E[X|Y]] = EX \]上式称作 全期望公式。
常用的套路以及技巧
\[\sum_{i=0}^nx^i=\frac{1=x^{n+1}}{1-x} \]当 \(n \rightarrow \infty\) 时：
\[\sum_{i=0}^{\infty}x^i=\frac{1}{1-x} \]前缀和技巧
对于离散变量， \(P(X = K) = P(X \leq K ) - P(x \leq k - 1)\)。
例 1
有 \(n\) 个随机变量 \(X_{1,\dots,n}\)，每个随机变量都是从 \(\lbrack 1,S \rbrack\) 中随机一个整数，求 \(\max(X_{1,\dots,n})\) 的期望。
\[\begin{aligned} E(\max) &= \sum_{i = 1}^S P(\max = i) \cdot i\\ &= \sum_{i=1}^S (P(\max \leq i) - P(\max \leq i - 1)) - 1\\ &= \sum_{i=1}^S \Big(\frac{i^n}{S^n} - \frac{(i-1)^n}{S^n} \Big) \cdot i \end{aligned} \]例 2
概率为 \(p\) 的事件期望 \(\displaystyle\frac{1}{p}\) 次之后发生。
\[\begin{aligned} E(X) &= \sum_i P(X = i) i \\ &= \sum_{i} P(X \ge i) - P(X \ge i + 1) \cdot i\\ &= \sum_{i} ((1 - p)^{i-1} - (1 - p) ^i) \cdots i \\ &= [(1 - p)^0 - (1-p)] + [(1-p)-(1-p)^2] + \dots \\ &= \sum_{i = 0} ^{\infty}(1-p)^i = \frac{1}{1-(1-p)} = \frac{1}{p} \end{aligned} \]拿球问题
例 1
箱子里有 \(i\) 个球 \(1 \dots n\)，你要从里面拿 \(m\) 次球，拿了后不放回，求取出的数字之和的期望。
解：
\[\sum_{i=1}^n P(i) \times i = \sum_{i = 1}^n\frac{m}{n} \times i= \frac{m}{n} \times \frac{n\times (n+1)}{2} = \frac{m \times (n + 1)}{2} \]例 2
箱子里有 \(i\) 个球 \(1 \dots n\)，你要从里面拿 \(m\) 次球，拿了后放回，求取出的数字之和的期望。
解
放不放回概率是一样的，所以：
\[ans = \frac{m\times (n + 1)}{2} \]例 3
箱子里有 \(n\) 个球 \(1 \dots n\)，你要从里边拿 \(m\) 次球，拿了之后有 \(\displaystyle\frac{1}{p_1}\) 的概率放回，求取出的球上数字和的期望。
解：
从拿了第一个球和第二个球来看，如果题目中没有要求有概率放回，如果是典例 \(1\) 的那种情况，第一次取得时候每一个球被取中的概率为 \(\displaystyle\frac{1}{n}\)，第二次取得时候每个球被取中的概率为 \(\displaystyle\frac{1}{n-1}\)。
如果加上限制，分别看两种情况。
看拿了第一个球之后，放回的概率就是 \(\displaystyle\frac{1}{p_1}\)，这个时候再拿第二个球每个球被取中的概率为 \(\displaystyle\frac{1}{p_1}\times\frac{1}{n}=\frac{1}{P_1n}\)。
我们把不放回的概率设为 \(\displaystyle \frac{p_1-1}{p_1}\)，如果不放回，取到每一个球的概率就是 \(\displaystyle\frac{n-1}{n}\times\frac{1}{n-1}\)，前后乘起来就是：\(\displaystyle\frac{p_1-1}{p_1n}\)。
两种情况算期望的时候为 \(P_1 \times i + P_2 \times i\)，会发现合并起来就是 \(\displaystyle\frac{1}{n} \times i\) ，和上边的一样，所以选 \(m\) 次的概率，选中 \(i\) 的概率还是 \(\displaystyle\frac{m}{n}\)。
\[ans = \frac{m \times {n + 1}}{2} \]游走问题
例 1
在一条 \(n\) 个点的链上游走，求从一端走到另一端的概率。
解：
用 \(X_i\) 表示 \(i\) 走到 \(i + 1\) 期望走多少步。
\[\begin{aligned} E(n) &= \sum_{i = 1}^n E(X_i) \\ E(X_i) &= \frac{1}{2} + \frac{1}{2} \times \Big(1 + E(X_{i - 1}) +E(X_i)\Big) \\ E(X_i) &= \frac{1}{2} + \frac{1}{2} + \frac{1}{2} \times E(X_{i - 1}) + \frac{1}{2} \times E(X_i) \\ E(X_i) &= E(X_{i - 1}) + 2 \\ E(n) &= 1 + 3 + 5 + \dots + 2 \times n - 3 = (n - 1) ^ 3 \end{aligned} \]例 2
在一个 \(n\) 个点的完全图上游走，求期望走多少步才能走到另一个点。
解：
每个点到其他点的概率都是 \(\displaystyle\frac{1}{n - 1}\)，所以期望就是 \(n - 1\) 次成功。
例 3
在一张 \(2 \times n\) 个点的完全二分图上游走，求从一个点走到另一个点的概率。
解：
左边等价，右边等价。
- 两点在同侧：\(\displaystyle\frac{1}{n} + \frac{n - 1}{n} \times (2 + A)\)。
- 两点在异侧：\(1 + A\)。
例 4
在一张 \(n\) 个点的菊花图上游走，求一个点走到另一个点的概率。
解：
- A.根到叶：\(\displaystyle\frac{1}{n - 1} + \frac{n - 2}{n - 1} \times (2 + A)\)。
- B.叶到根：\(1\)。
- C.叶到叶：\(A + 1\)。
例 5
在一棵 \(n\) 个点的树上游走，求从根节点走到 \(x\) 的期望步数。
解：
\(X_i\) 表示从 i 点游走，走到 \(father_i\) 的期望步数，\(d_i\) 为 \(i\) 的入度。
\[f_x = \frac{1}{d_x} + \frac{1}{d_x} \times \sum_{i = 1}^{d_x} (1 + f_{son_x} + f_x) \]经典问题
例 1
每次随机取一个 \([1,n]\) 的整数，问期望多少次能够凑齐所有的数。
解： 考虑每次取得时候取中以前没取过的数的概率，显然是 \(\displaystyle\sum_{i=1}^n\frac{n-i}{n}\)。
上边那个东西也等于 \(\displaystyle\sum_{i=1}\frac{i}{n}\)，期望就是 \(\displaystyle\sum_{i=1}\frac{n}{i}\) 。
例 2
随机一个长度为 \(n\) 的排列 \(p\)，求 \(P_1.\dots, P_i\) 中的最大值为 \(P_i\) 的概率。
解：
\(\displaystyle \sum_{i = 1}^n \frac{1}{n}\)。
每个前缀中，最大值都有 \(i\) 个位置可以选，所以是 \(\displaystyle\frac{1}{i}\)。
例 3
随机一个长度为 \(n\) 的排列 \(p\)，求 \(i\) 在 \(j\) 后边的概率。
解：
\(\displaystyle\frac{1}{2}\)，挺显然的。
例 4
随机一个长度为 \(n\) 的排列 \(p\)，求它包含 \(w_{i}, i \in [1,m]\) 为子序列 / 子串的概率。
- 子序列，\(\left(\begin{array}{c}n\\m\end{array}\right)\displaystyle\times\frac{(n - m)!}{n!}=\frac{1}{m!}\)，把他想想象成很多方块，每个方块都能放一个数，因为是子序列，就从里边选 \(m\) 个块，放这个子序列，剩下的可以随便放，挺显然的。
- 子串，\(\displaystyle (n - m + 1) \times \frac{(n - m)!}{n!} = \frac{(n - m + 1)!}{n!}\)，考虑剩下的 \(n-m\) 个数都放好了，有 \(\displaystyle\frac{(n - m)!}{n!}\) 种方案，然后从 \(n - m + 1\) 个空中任选一个插入长度为 \(m\) 的子串，就是上边那个式子。