概率与数学期望

样本、样本空间、随机事件和随机变量

在概率论中，我们把一个随机实验的某种可能结果称为一个 样本，把所有可能结果构成的集合称为 样本空间，一般记为 $S$。$S$ 中的元素即为实验的每一个结果，称为 样本点。在一个给定的样本空间中，我们把若干个样本构成的集合，即样本空间的子集，称为 随机事件。在每次试验中，当且仅当这一子集中的一个样本点出现时，称这一事件“发生”。有一个样本点组成的单个元素的集合，称为 基本事件。$S$ 是自身的子集，在每次试验中必然发生，称为 必然事件。空集 $\varnothing$ 也是 $S$ 的一个子集，在每次试验中都不可能发生，称为 不可能事件。

我们把将样本映射为实数的函数称为 随机变量。当随机变量的取值有限时，我们称该随机变量为 离散型随机变量，反之当随机变量的取值无限时，我们称该随机变量为 连续型随机变量。

概率

定义

概率有多种定义，如 古典定义、统计定义 和 公理化定义。

古典定义

如果一个试验满足两条：

1. 试验只有有限个基本结果；
2. 试验的每个基本结果出现的可能性是一样的；

这样的试验便是古典试验。

对于古典试验中的事件 $A$，它的概率定义为 $P(A)=\dfrac{m}{n}$，其中 $n$ 表示该试验中所有可能出现的基本结果的总数目，$m$ 表示事件 $A$ 包含的试验基本结果数。

公理化定义

设样本空间为 $\Omega$，如果对于 $\Omega$ 中的每一个随机事件 $A$，都存在实值函数 $P(A)$，满足：

1. $P(A) \ge 0$。
2. $P(\Omega)=1$。
3. 对于若干个两两互斥事件 $A_i$，有 $\sum P(A_i)=P(\bigcup A_i)$，其中 $\bigcup$ 表示并集。

则称 $P(A)$ 为随机事件 $A$ 发生的概率。通俗来说，概率就是对随机事件发生可能性的度量，是一个 $[0,1]$ 之间的实数。

条件概率

记 $P(B|A)$ 表示在 $A$ 事件发生的前提下，$B$ 事件发生的概率，则 $P(B|A)=\dfrac{P(AB)}{P(A)}$（其中 $P(AB)$ 为事件 $A$ 和事件 $B$ 同时发生的概率）。

独立事件

当两个事件发生的概率互不影响时，我们称这两个事件互为独立事件。更规范来说，我们称事件 $A$ 和事件 $B$ 互为独立事件，当且仅当 $P(A|B)=P(A)$。

独立变量

对于两个变量 $x,y$，我们称 $x$ 和 $y$ 是相互独立的当且仅当 $\forall a,b,P(x=a \cap y=b)=P(x=a)P(y=b)$，更进一步的，$E(xy)=E(x)(y)$。

概率的性质

1. $P(\emptyset)=0$。
2. （有限可加性）当 $n$ 个事件 $A_1,A_2,\cdots,A_n$ 两两不相容时，$P(A_1 \cup A_2 \cup \cdots \cup A_n)=P(A_1)+P(A_2)+\cdots+P(A_n)$。
3. 对于任意一个事件 $A$，$P(A)=1-P(!A)$。
4. 当事件 $A$ 包含于 $B$ 时，$P(B-A)=P(B)-P(A)$ 且 $P(A) \le P(B)$。
5. 对于任意两个事件 $A$ 和 $B$，$P(B-A)=P(B)-P(A \cap B)$。
6. （广义加法公式）对于任意两个事件 $A$ 和 $B$，$P(A \cup B)=P(A)+P(B)-P(A \cap B)$。
7. （乘法公式）对于任意两个事件 $A$ 和 $B$，$P(AB)=P(A)P(B|A)$。

全概率公式

若事件 $A_1,A_2,\cdots,A_n$ 构成一组完备的事件且都有正概率，即 $\forall i,j|A_i \cap A_j=\emptyset$ 且 $\sum\limits_{i=1}^nA_i=1$，则有 $P(B)=\sum\limits_{i=1}^nP(A_i)P(B|A_i)$。

贝叶斯公式

若事件 $B_1,B_2,\cdots,B_n$ 构成一组完备的事件且都有正概率，即 $\forall i,j|B_i \cap B_j=\emptyset$ 且 $\sum\limits_{i=1}^nB_i=1$，则有 $P(B_i|A)=\dfrac{P(B_i)P(A|B_i)}{\sum\limits_{j=1}^nP(B_j)P(A|B_j)}$。

证明：（使用条件概率和全概率公式）

$$\begin{aligned} P(B_i|A) &= \dfrac{P(AB_i)}{P(A)} \\ &= \dfrac{P(B_i)P(A|B_i)}{\sum\limits_{j=1}^nP(B_j)P(A|B_j)} \end{aligned}$$

期望

定义

（本文以介绍离散型随机变量为主。）

离散型随机变量的数学期望

一个离散型随机变量 $X$ 的 数学期望 是其每个取值乘以该取值对应概率的总和，记为 $E(X)$。

$$E(X)=\sum\limits_{\alpha \in I(X)} \alpha\cdot P(X=\alpha)=\sum\limits_{\omega \in S}X(\omega)P(\omega)$$

其中 $I(X)$ 表示随机变量 $X$ 的值域，$S$ 表示 $X$ 所在概率空间的样本集合。

连续型随机变量的数学期望

若有一个连续型随机变量 $X$ 取值为 $\xi$ 的概率为 $p(\xi)$，则定义其期望 $E(X)$ 为：

$$E(X)=\int_{-\infty}^{+\infty}Xp(X)\mathrm{d}X$$

性质

全期望公式

$E(Y)=\sum\limits_{\alpha \in I(X)} P(X=\alpha)E(Y|(X=\alpha))$，其中 $X,Y$ 是随机变量，$E(Y|A)$ 是在 $A$ 成立的条件下 $Y$ 的期望（即“条件期望”）。

期望的线性性

对于任意两个随机变量 $X,Y$（不要求相互独立），有 $E(X+Y)=E(X)+E(Y)$。

证明：我们把 $\sum\limits_x$ 和 $\sum\limits_y$ 当作 $\sum\limits_{x \in I(X)}$ 和 $\sum\limits_{y \in I(Y)}$ 的简称。那么：

$$\begin{aligned} E(X+Y) &= \sum\limits_x\sum\limits_y(x+y)P(X=x,Y=y) \\ &= \sum\limits_x\sum\limits_yxP(X=x,Y=y)+\sum\limits_x\sum\limits_yyP(X=x,Y=y) \\ &= \sum\limits_xx\sum\limits_yP(X=x,Y=y)+\sum\limits_yy\sum\limits_xP(X=x,Y=y) \\ &= \sum\limits_xxP(X=x)+\sum\limits_yyP(Y=y) \\ &= E(X)+E(Y) \end{aligned}$$

乘积的期望

对于任意两个相互独立的随机变量 $X,Y$，有 $E(XY)=E(X)E(Y)$。

证明：我们把 $\sum\limits_x$ 和 $\sum\limits_y$ 当作 $\sum\limits_{x \in I(X)}$ 和 $\sum\limits_{y \in I(Y)}$ 的简称。那么：

$$\begin{aligned} E(XY) &= \sum\limits_x\sum\limits_y(xy)P(X=x,Y=y) \\ &= \sum\limits_xx\sum\limits_yyP(X=x,Y=y) \\ &= \sum\limits_xxP(X=x)\sum\limits_yyP(Y=y) \\ &= E(X)E(Y) \end{aligned}$$

经典题目和结论

首次期望

对于一个随机事件 $A$，它成功的概率为 $P(A)$。那么，第一次成功所需的次数的期望值为 $\dfrac{1}{P(A)}$。

证明：考虑枚举第 $1$ 次成功，第 $2$ 次成功等等的可能性。

$E(A)=\sum\limits_{i=1}^{+\infty}(i \times (1-P(A))^{i-1} \times P(A))$

考虑错位相减消项

$\begin{aligned} E(A)(1-P(A)) &= P(A)\sum\limits_{i=1}^{+\infty}i(1-P(A))^i \\ &= P(A)\sum\limits_{i=2}^{+\infty}(i-1)(1-P(A))^{i-1} \end{aligned}$

将上面两式相减

$\begin{aligned} E(A)P(A) &= P(A)(1+\sum\limits_{i=2}^{\infty}(1-P(A))^{i-1}) \\ &= P(A)\sum\limits_{i=1}^{+\infty}(1-P(A))^{i-1} \end{aligned}$

再用等比数列求和公式

$\begin{aligned} E(A) &= \sum\limits_{i=1}^{+\infty}(1-P(A))^{i-1} \\ &= \dfrac{(1-P(A))^0}{1-(1-P(A))} \\ &= \dfrac{1}{P(A)} \end{aligned}$

取球问题

取球问题 1

箱子里有 $n$ 个球 $1 \dots n$，你要从中拿 $m$ 次球，拿了后不放回，求取出的数字之和的期望。

取球问题 2

箱子里有 $n$ 个球 $1 \dots n$，你要从中拿 $m$ 次球，拿了后放回，求取出的数字之和的期望。

取球问题 3

箱子里有 $n$ 个球 $1 \dots n$，你要从中拿 $m$ 次球，拿了后有 $P$ 的概率放回，有 $1-P$ 的概率不放回，求取出的数字之和的期望。

随机游走问题

链上的随机游走

在一条 $n$ 个点的链上随机游走，求从一端走到另一端的期望步数。

完全图上的随机游走

在一条 $n$ 个点的完全图上随机游走，求从一点走到另一点的期望步数。

完全二分图上的随机游走

在一条 $2n$ 个点的完全二分图上随机游走，求从一点走到另一点的期望步数。

菊花图上的随机游走

在一条 $n$ 个点的菊花图上随机游走，求从一点走到另一点的期望步数。

树上的随机游走

在一条 $n$ 个点的树上随机游走，求从一点走到另一点的期望步数。（设计算法）

例题：简单概率

例题：期望的线性性

例题：简单期望 DP / 手算方程

例题：链上 / 环上随机游走

例题：树上随机游走的期望次数

例题：与 $\max$、$\min$ 有关的二分技巧

参考资料

• 概率期望知识点及题目详解 - wxyww - 博客园
• 浅谈期望的线性性（可加性）【CodeForces280c】【bzoj3036】【bzoj3143】 - LinnBlanc - 博客园
• 正睿19暑期B班DAY1-1 概率与期望 - hjmmm - 博客园