zehua

Zehua

概率论基础

机器学习
0
0
2025-03-22

基本概念

概述

在研究随机现象时，我们通常关注以下几个核心要素：

  • 样本空间 \Omega ：表示该随机现象中所有可能出现的结果。

  • 事件域 \mathcal{F} ：指我们所关心的所有事件的集合。

  • 概率 P ：用于描述各个事件发生的可能性大小。

样本空间与随机事件

定义

在一个随机现象中，每一个不能再细分的基本结果称为样本点。所有样本点的集合构成样本空间，通常记作 \Omega 。

我们关心的随机事件，可以看作是样本空间中的某个子集，由若干样本点组成，常用大写字母如 A, B, C, \cdots 表示。

当某个具体结果 \omega 属于事件 A ，即 \omega \in A ，我们就说 事件 A 发生了 。

例如，掷一次骰子，这个实验的样本空间是 \Omega = {1, 2, 3, 4, 5, 6} ，设事件 A 表示 “点数大于 4”，那么 A = {5, 6} ，如果实际结果是 \omega = 3 ，由于 3 \notin A ，所以事件 A 并没有发生。

事件的运算

由于事件被定义为样本空间的子集，我们可以直接使用集合运算（如交集、并集、补集等）来描述事件之间的关系。

通常采用与集合一致的记号：

  • 并集： A \cup B ，表示“事件 A 或 B 发生”，也常记作 A + B ，称为和事件。

  • 交集： A \cap B ，表示“事件 A 与 B 同时发生”，也可记作 AB ，称为积事件。

事件域

在研究具体的随机现象时，我们通常不会关心所有可能的事件，而是会事先明确哪些事件是我们感兴趣的。根据随机事件的定义，事件域 \mathcal{F} 应该是样本空间 \Omega 的某些子集的集合，也就是说， \mathcal{F} \subset 2^{\Omega} ，其中 2^{\Omega} 表示由 \Omega 的所有子集组成的集合族。

虽然 \mathcal{F} 包含于 2^{\Omega} ，但它不一定等于 2^{\Omega} 。这一点在样本空间 \Omega 有限时可能不太明显，因为此时 2^{\Omega} 虽然更大，但仍是有限集合；而当 \Omega 是无穷集合时， 2^{\Omega} 的规模会变得极其庞大，其中还可能包含一些 不太好处理 或我们并不关心的事件。为了避免在概率运算中遇到这些“麻烦事件”，我们通常会选择一个更小、更具良好结构的子集族作为我们的事件域 \mathcal{F} 。

需要注意的是，虽然事件域 \mathcal{F} 不要求等于 2^{\Omega} ，但也不是任何子集族都可以作为事件域。为了保证我们能对感兴趣的事件进行各种基本的概率运算，我们希望事件域满足以下条件：

  1. \varnothing \in \mathcal{F} （空事件必须包含在内）；

  2. 若 A \in \mathcal{F} ，则其补集 \bar{A} \in \mathcal{F} （对补封闭）；

  3. 若有一列事件 A_n \in \mathcal{F} ， n = 1, 2, 3, \dots ，则它们的并集 \bigcup A_n \in \mathcal{F} （对可数并封闭）。

简而言之，事件域 \mathcal{F} 必须满足：包含空集、对补运算封闭、以及对可数并封闭。事实上，可以证明：如果一个集合族满足这三条性质，它对可数交集也是封闭的。

示例

考虑掷一颗六面骰子，其样本空间为 \Omega = {1, 2, 3, 4, 5, 6} 。下面几个集合是事件域的例子：

  • \mathcal{F}_1 = {\varnothing, \Omega} ：只包含必然事件和不可能事件，满足所有要求。

  • \mathcal{F}_2 = {\varnothing, {1, 3, 5}, {2, 4, 6}, \Omega} ：包含奇数点数、偶数点数及其相关事件，也满足封闭性条件。

但以下两个集合则不能作为事件域：

  • \mathcal{F}_3 = {\varnothing, {1}, \Omega} ：对补运算不封闭（ {1} 的补集 {2,3,4,5,6} 不在其中）。

  • \mathcal{F}_4 = {{1,3,5}, {2,4,6}} ：不包含 \varnothing ，且对并集运算也不封闭（两者的并是整个 \Omega ，但它不在集合中）。

 

概率

定义

古典定义

在概率论发展的早期，人们研究的多是一些较为简单的随机现象，这类情形的样本空间 \Omega 是有限集合，并且每个基本结果直观上看都是等可能发生的。在这种前提下，概率被定义为：

若一个随机现象满足：

  1. 样本空间中只有有限个基本事件；

  2. 所有基本事件发生的可能性相同；

则对于任意事件 A ，其概率定义为：

P(A) = \frac{\#(A)}{\#(\Omega)}

其中， \#(\cdot) 表示集合中元素的个数，即事件中包含的样本点数。

这一定义清晰直观，也为后续更复杂模型提供了基础。例如在几何概型中，我们可以将 个数 替换为 长度 面积 等连续度量，从而在某些无限样本空间的情形下推广这一思路。

公理化定义

尽管古典定义在有限样本空间中适用良好，但它在逻辑上存在一定问题。定义 概率 时使用了 可能性 等直觉性概念，容易产生循环定义；而 等可能性 在无限样本空间中也难以成立。这些问题引发了包括Bertrand 悖论在内的一系列矛盾。

为了解决这些基础性问题，苏联数学家柯尔莫哥洛夫（Kolmogorov）于 1933 年在其著作《概率论基础》中提出了概率的公理化定义，从而确立了现代概率论的数学框架。

根据柯尔莫哥洛夫的定义，概率是一个函数 P ，它将事件域 \mathcal{F} 中的每个事件映射到区间 [0,1] 上，满足以下三条公理：

  1. 规范性（或非负性）：

    P(\Omega) = 1

    即整个样本空间发生的概率为 1。

  2. 可数可加性：

    若事件 A_1, A_2, \cdots 两两互不相交（即 A_i \cap A_j = \varnothing ，当 i \ne j ），则有：

    P\left( \bigcup_{i=1}^{\infty} A_i \right) = \sum_{i=1}^{\infty} P(A_i)

概率的基本性质

在上述公理基础上，可以推出一系列常用的概率性质。对于任意事件 A, B \in \mathcal{F} ，有：

  • 单调性：

    若 A \subset B ，则：

    P(A) \leq P(B)

  • 容斥原理（二元）：

    P(A \cup B) = P(A) + P(B) - P(A \cap B)

  • 差事件的概率：

    P(A - B) = P(A) - P(A \cap B)

    其中， A - B 表示事件 A 发生而 B 不发生的情形。

 

概率空间

在概率论中，我们在研究一个具体的随机现象时，通常关注以下三个基本要素：

  • 样本空间 \Omega ：描述所有可能的基本结果；

  • 事件域 \mathcal{F} ：指定哪些事件是我们关心的；

  • 概率函数 P ：赋予每个事件一个发生的概率。

这三者共同构成了概率论的基本结构，我们将三元组：

(\Omega, \mathcal{F}, P)

称为一个概率空间（probability space）。

只有在一个明确的概率空间中，讨论概率才有意义。如果缺乏对样本空间或事件域的清晰定义，概率的计算和解释就会变得模糊甚至产生矛盾。例如我们之前提到的 Bertrand 悖论，其实质就在于对样本空间 \Omega 的定义不够明确：不同的建模方式对应不同的样本空间，从而得到不同的概率结果

 

 

条件概率与独立性

在很多实际问题中，某些事件的发生概率会随着已知信息的增加而发生变化。举个例子，抽卡，我们可能起初认为出 金色传说！ 与 稀有！ 的概率是相等的。但如果已经连续抽了 50 次都没有出六星，就说明他们概率肯定不一样，金色传说概率就是小。

因此，研究在某些条件下事件发生的概率是非常有必要的，这就是条件概率的研究动机。

条件概率

定义

在概率空间 (\Omega, \mathcal{F}, P) 中，若已知事件 A \in \mathcal{F} 且 P(A) > 0 ，我们定义在事件 A 已经发生的前提下，事件 B 发生的概率为条件概率，记作 P(B|A) ，其定义为：

P(B|A) = \frac{P(AB)}{P(A)}, \quad \forall B \in \mathcal{F}

可以验证：对于固定的 A ，函数 P(\cdot | A) 满足概率的三个公理，因此它是事件域 \mathcal{F} 上的一个概率函数。

推论

从条件概率的定义可以直接推出以下两个重要的公式：

概率乘法公式

在概率空间 (\Omega, \mathcal{F}, P) 中，若 P(A) > 0 ，则对任意事件 B 有：

P(AB) = P(A)P(B|A)

全概率公式

设事件组 A_1, A_2, \dots, A_n 两两互不相交，且它们的并为整个样本空间，即：

\bigcup_{i=1}^n A_i = \Omega

那么对任意事件 B ，有：

P(B) = \sum_{i=1}^n P(A_i)P(B|A_i)

Bayes 公式

在某些问题中，我们可能先知道各个事件 A_1, A_2, \dots, A_n 导致事件 B 发生的可能性（即 P(B|A_i) ），以及这些事件本身的概率 P(A_i) ，可以通过全概率公式求出 P(B) 。而如果我们想反过来，在事件 B 已发生的前提下，判断是哪一个 A_i 导致的，就可以用Bayes 公式：

P(A_i|B) = \frac{P(A_iB)}{P(B)} = \frac{P(A_i)P(B|A_i)}{\sum_{j=1}^n P(A_j)P(B|A_j)}

事件的独立性

在研究条件概率的过程中，我们可能会遇到这样的情况： P(B|A) = P(B) 。这意味着在已知事件 A 发生的前提下，事件 B 发生的概率没有变化——也就是说，事件 A 的发生与事件 B 没有关系。

定义

在同一概率空间中，若事件 A, B 满足：

P(AB) = P(A)P(B)

则称 A 与 B 独立。

多个事件的独立性

对于多个事件 A_1, A_2, \dots, A_n ，我们称它们相互独立，当且仅当任取任意 r 个不同的事件 A_{i_1}, A_{i_2}, \dots, A_{i_r} ，都有：

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) = \frac{1}{2}

以及：

P(AB) = P(BC) = P(CA) = P(ABC) = \frac{1}{4}

从中可以看出， A, B, C 两两独立，但：

P(ABC) = \frac{1}{4} \neq \frac{1}{8} = P(A)P(B)P(C)

因此， A, B, C 虽然两两独立，但不相互独立。

 

 

 

随机变量

相关概念

随机变量的定义

在给定的概率空间 (\Omega, \mathcal{F}, P) 中，若一个定义在样本空间 \Omega 上的函数 X : \Omega \to \mathbb{R} 满足：

\{ \omega \in \Omega : X(\omega) \le t \} \in \mathcal{F}, \quad \forall t \in \mathbb{R}

则称 X 为一个随机变量。

直观上，随机变量是将样本空间中的每个样本点映射到实数轴上的函数，同时这个映射要 保持可测性 ，即其诱导的集合属于事件域 \mathcal{F} 。

示性函数

给定事件 A \subseteq \Omega ，定义其示性函数（Indicator Function） I_A(\omega) 为：

I_A(\omega) = \begin{cases} 1, & \omega \in A \\ 0, & \omega \notin A \end{cases}

这是最简单的一类随机变量，用于描述事件是否发生。

分布函数

对于随机变量 X ，我们定义函数：

F(x) = P(X \le x)

称 F(x) 为 X 的分布函数，记作 X \sim F(x) 。

分布函数的性质：

  1. 右连续性：

    \lim_{t \to x^+} F(t) = F(x)

  2. 单调递增： F(x) 在 \mathbb{R} 上单调递增（非严格）。

  3. 极限值：

    \lim_{x \to -\infty} F(x) = 0, \quad \lim_{x \to +\infty} F(x) = 1

实际上，任何满足上述三个条件的函数 F(x) ，都对应某个随机变量的分布函数。因此，分布函数与随机变量之间具有一一对应的关系。

随机变量的分类

根据随机变量取值的不同方式，可以将其分为：

离散型随机变量

若随机变量 X 的取值集合为至多可数的一组实数 \{x_1, x_2, \dots\} ，则称其为离散型随机变量。此时，我们可列出其概率分布：

P(X = x_i) = p_i, \quad \sum_{i} p_i = 1

这就是我们在高中课中学的分布列。

连续型随机变量

对于连续型随机变量 X ，单点处的概率通常为 0，即：

P(X = x) = 0

尽管如此，我们仍可以考察其在一个区间内的概率：

P(l < X \le l + \Delta x) = F(l + \Delta x) - F(l)

进一步地，当 \Delta x \to 0^+ ，可以用导数来近似描述分布的局部变化：

f(x) = \lim_{\Delta x \to 0^+} \frac{F(x + \Delta x) - F(x)}{\Delta x}

如果这个极限存在，称 f(x) 为 X 的概率密度函数，且有：

F(x) = \int_{-\infty}^{x} f(t)\,\mathrm{d}t

随机变量的独立性

之前讨论了事件的独立性。由于随机变量本质上是从样本空间到实数的函数，我们可以类似地定义随机变量之间的独立性。

定义

若两个随机变量 X 和 Y 满足：

P(X \le x, Y \le y) = P(X \le x) \cdot P(Y \le y) \quad \forall x, y \in \mathbb{R}

则称 X 与 Y 相互独立。

Note： 有些教材（尤其是中学课本）中给出的独立性定义是：

P(X = x, Y = y) = P(X = x) \cdot P(Y = y)

这个定义在离散型随机变量中是成立的，但在连续情形中， P(X = x) = 0 导致其不适用。因此，使用分布函数的定义更为一般、合理。

性质

若随机变量 X 与 Y 相互独立，则对于任意函数 f(X) 与 g(Y) ，这两个新的随机变量也是独立的。

Note：

尽管 X 与 Y 独立，但它们的函数组合 f(X, Y) 并不一定与其中某一变量的函数独立。例如， XY^2 与 X 并不一定独立，不能简单代入分析。

随机变量的数字特征

期望

定义

离散型随机变量

设离散型随机变量 X 的概率分布为 P\{ X = x_i \} = p_i ，若级数 \sum x_i p_i 绝对收敛，则称该值为 X 的期望，记作 \mathbb{E}[X] 或 EX 。

连续型随机变量

设连续型随机变量 X 的概率密度函数为 f(x) ，若积分 \int_{\mathbb{R}} x f(x)\,\mathrm{D}[X] 绝对收敛，则称该值为 X 的期望，记作 \mathbb{E}[X] 。

统一定义（Stieltjes 积分形式）

设随机变量 X 的分布函数为 F(x) ，若积分 \int_{\mathbb{R}} x\, \mathrm{d}F(x) 绝对收敛，则定义该值为 X 的期望，记作 \mathbb{E}[X] 。这一形式统一涵盖了离散型和连续型的定义。

期望不存在的例子

例 1（离散型）：

设随机变量 X 的分布为：

P\left( X = (-1)^k \cdot \frac{2^k}{k} \right) = \frac{1}{2^k}, \quad k = 1, 2, 3, \dots

虽然级数 \sum x_i p_i 条件收敛且和为 - \ln 2 ，但因其不是绝对收敛的，所以期望不存在。

例 2（连续型）：

设连续型随机变量 Y 的密度函数为：

f(y) = \frac{1}{\pi} \cdot \frac{1}{1 + y^2}, \quad y \in (-\infty, +\infty)

这是著名的柯西分布，它的期望也不存在，因为对应的积分不收敛。

期望的性质

线性性质

若随机变量 X, Y 的期望存在，则对于任意实数 a, b ，有：

\mathbb{E}(aX + b) = a \cdot \mathbb{E}[X] + b
\mathbb{E}(X + Y) = \mathbb{E}X + \mathbb{E}Y

 

随机变量乘积的期望

若 X 和 Y 相互独立，且期望存在，则有：

\mathbb{E}(XY) = \mathbb{E}X \cdot \mathbb{E}Y

注意：这个等式在某些情况下即使 X, Y 不独立也可能成立。但在一般讨论中，独立性是最常用的充分条件。

反例说明

设 X \sim \text{Unif}[-1, 1] ，即 X 在区间 [-1, 1] 上均匀分布，设 Y = X^2 。

显然 X 和 Y 并不独立，但我们仍有：

\mathbb{E}(XY) = \mathbb{E}(X^3) = 0, \quad \mathbb{E}X = 0, \quad \mathbb{E}Y = \mathbb{E}(X^2) = \frac{1}{3}

因此， \mathbb{E}(XY) = \mathbb{E}[X] \cdot \mathbb{E}Y 成立，尽管 X, Y 并不独立。

期望与概率的转化

设事件 A ，定义其示性函数 I_A 为：

I_A(\omega) = \begin{cases} 1, & \omega \in A \\ 0, & \omega \notin A \end{cases}

由定义可知：

\mathbb{E}[I_A] = P(A)

这是一种在建模和计算中非常常用的技巧：将事件概率转化为期望计算。

例子：期望的线性性简化计算

假设一个长度为 n 的序列 \{ a_i \} ，其中每个 a_k 以概率 p_k 取值 k ，以概率 1 - p_k 取值 0。我们要计算 S = \sum_{i=1}^{n} a_i 的期望。

若直接从定义入手，需穷举 S 的所有可能取值及其对应概率，计算复杂。但我们可以采用如下简化策略：

定义事件 A_k 表示 a_k = k ，则可令 I_k 为事件 A_k 的示性函数，于是：

S = \sum_{k=1}^{n} k \cdot I_k

利用线性性质：

\mathbb{E}[S] = \mathbb{E} \left( \sum_{k=1}^{n} k \cdot I_k \right) = \sum_{k=1}^{n} k \cdot \mathbb{E}[I_k] = \sum_{k=1}^{n} k \cdot p_k

这样，大大简化了求解过程。

 

条件分布与条件期望

条件分布

设 (X, Y) 是一对随机变量，在已知 Y = y 的条件下， X 的概率分布（或密度）称为 X 在给定 Y = y 条件下的条件分布，分别记作：

  • 离散情形： P(X = x_i \mid Y = y)

  • 连续情形： f_{X|Y}(x \mid y)

在此条件下， X 的期望称为条件期望，记作：

\mathbb{E}[X \mid Y = y]

进一步推广，当我们不固定 Y 的具体值时，条件期望 \mathbb{E}[X \mid Y] 表示在 Y 给定的情形下 X 的期望，是 Y 的函数，通常为随机变量。

条件期望的性质

  • 条件期望 \mathbb{E}[X \mid Y] 通常是 Y 的非线性函数。

  • 最重要的性质之一是全期望公式（Law of Total Expectation）：

    \mathbb{E}[\mathbb{E}[X \mid Y]] = \mathbb{E}[X]

应用示例

例题：[LA 7736] Pocky 问题

一根长为 L 的 Pocky，每次随机折成两段。若右段长度不超过 d 则停止；否则，对右段重复该操作。求重复折断的期望次数。

设 f(x) 表示长度为 x 时的期望次数， x \le d 时显然有 f(x) = 0 。

对于 x > d ，设折断点距右端的长度为 k ，由于折断点在 [0, x] 上均匀分布，有：

k \sim U[0, x]

期望的重复次数为：

g(k) = \begin{cases} 1, & k \le d \\ 1 + f(k), & k > d \end{cases}

根据全期望公式：

f(x) = \mathbb{E}[g(k)] = 1 + \frac{1}{x} \int_d^x f(t)\,\mathrm{d}t

解该积分方程并结合边界条件，可得：

f(x) = 1 + \ln\left( \frac{x}{d} \right)

方差

定义

设随机变量 X 的期望 \mathbb{E}[X] 存在，且下式也存在：

\mathbb{E}[(X - \mathbb{E}X)^2]

则称该值为 X 的方差，记作 \mathrm{D}[X] 或 \mathrm{Var}(X) 。

方差的平方根称为标准差，记作：

\sigma(X) = \sqrt{\mathrm{D}X}

方差的性质

若 X 的方差存在，则对任意常数 a, b 有：

\mathrm{D}(aX + b) = a^2 \cdot \mathrm{D}X
\mathrm{D}[X] = \mathbb{E}[X^2] - (\mathbb{E}X)^2

协方差与相关系数

协方差（Covariance）

为研究多个变量间的线性关系，引入协方差，设 X, Y 是两个随机变量，其协方差定义为：

\operatorname{Cov}(X, Y) = \mathbb{E}[(X - \mathbb{E}X)(Y - \mathbb{E}Y)]

协方差的性质

  • 对称性： \operatorname{Cov}(X, Y) = \operatorname{Cov}(Y, X)

  • 线性性：对任意常数 a, b 有：

    \operatorname{Cov}(aX + bY, Z) = a \cdot \operatorname{Cov}(X, Z) + b \cdot \operatorname{Cov}(Y, Z)

  • 与方差的关系：

    \mathrm{D}X = \operatorname{Cov}(X, X)

  • 两变量求和的方差：

    \mathrm{D}(X + Y) = \mathrm{D}X + 2\operatorname{Cov}(X, Y) + \mathrm{D}Y

几何意义

协方差在形式上与向量内积相似。在泛函分析中，概率空间上的随机变量可看作一个向量空间，协方差就是其中的 内积，标准差则是由此导出的 范数。

相关系数

为进一步刻画协方差的大小，引入标准化的指标：

\rho_{X,Y} = \frac{\operatorname{Cov}(X, Y)}{\sigma(X)\sigma(Y)}

称为Pearson 相关系数，其取值范围：

-1 \le \rho_{X,Y} \le 1

  • 当 \rho_{X,Y} = 1 ，表示 X, Y 完全正相关，即存在 a, b > 0 使得：

    P(X = a + bY) = 1

  • 当 \rho_{X,Y} = -1 ，表示完全负相关，即 P(X = a - bY) = 1

  • 当 \rho_{X,Y} = 0 ，则称 X 与 Y 不相关（uncorrelated）

不相关 ≠ 独立

两个随机变量不相关，意味着它们没有线性关系，但并不代表它们之间完全无关。 独立性是更强的条件：若 X 与 Y 独立，则一定不相关，但反之不成立。

 

 

概率不等式

在算法竞赛中，随机化算法是一类常见且强大的工具。这些算法的正确性与运行效率通常建立在一个前提上：某些“坏事件”发生的概率非常小。 例如，快速排序的时间复杂度依赖于一个事实：所选的 pivot 元素极少是当前序列中的最大值或最小值。因此，在分析这类算法时，概率不等式成为不可或缺的工具。

本文将简要介绍几种常用的不等式，并通过简单例子展示其应用。

Union Bound（并集不等式）

设 A_1, A_2, \dots, A_m 是一组随机事件，则它们的并的概率满足：

P\left( \bigcup_{i=1}^m A_i \right) \le \sum_{i=1}^m P(A_i)

这称为并集不等式，也常被称为Boole 不等式或Union Bound。

直观理解：一组事件中至少有一个发生的概率，不超过所有事件发生概率之和。

加强形式：容斥不等式（Inclusion-Exclusion Bound）

实际上，除了上述上界外，我们还可以给出一组事件联合发生概率的更紧上下界。这种方式可以看作是容斥原理的不完全展开：

  • 下界：

    P\left( \bigcup_{i=1}^m A_i \right) \ge \sum_{i=1}^m P(A_i) - \sum_{1 \le i < j \le m} P(A_i \cap A_j)

  • 上界（更紧）：

    P\left( \bigcup_{i=1}^m A_i \right) \le \sum_{i=1}^m P(A_i) - \sum_{1 \le i < j \le m} P(A_i \cap A_j) + \sum_{1 \le i < j < k \le m} P(A_i \cap A_j \cap A_k) - \cdots

这样的展开可以无限进行，层层交替给出上下界，直到包含所有 m 项为止，即为完全的容斥公式。

虽然容斥的精度更高，但在算法分析中，为了简洁常常只取最前面一两项来估计或界限概率。

应用举例

示例：分析快速排序期望复杂度

设我们每次随机选取 pivot，分析 最坏情况 ——即 pivot 是当前区间的最大值或最小值。该事件在 n 个元素中发生的概率为 \frac{2}{n} 。

若我们分析一次排序过程，考虑从 i = 1 到 n 的 n-1 次划分，则：

P(\text{出现最坏情况至少一次}) \le \sum_{i=1}^{n-1} \frac{2}{i+1} < 2 \cdot \sum_{i=2}^{n} \frac{1}{i} \approx 2 \ln n

这说明虽然个别事件发生概率较高，但整体 坏情况 出现的总概率可控，从而保证算法在期望意义下表现良好。

 

Markov 不等式

设 X 是一个取值非负的随机变量（即 X(\omega) \ge 0, \ \forall \omega ），则对任意正实数 a > 0 ，有：

P\{ X \ge a \} \le \frac{\mathbb{E}X}{a}

这个不等式被称为Markov 不等式。

由于该不等式只使用了随机变量的期望 \mathbb{E}[X] ，而没有使用更具体的分布信息，因此其结论通常比较宽松，但在理论分析中依然非常有用，尤其适合用于上界估计。

证明

设事件 A = \{ X \ge a \} ，记其示性函数为 I_A ，则我们有：

I_A(\omega) = \begin{cases} 1, & X(\omega) \ge a \\ 0, & \text{otherwise} \end{cases} \quad \Rightarrow \quad I_A \le \frac{X}{a}

两边取期望，有：

P\{ X \ge a \} = \mathbb{E}[I_A] \le \mathbb{E}\left[ \frac{X}{a} \right] = \frac{\mathbb{E}[X]}{a}

Chebyshev 不等式

设随机变量 X 的期望 \mathbb{E}[X] 存在，方差 \mathrm{D}[X] 也存在。则对任意正数 a > 0 ，有：

P\{ |X - \mathbb{E}[X]| \ge a \} \le \frac{\mathrm{D}[X]}{a^2}

这是著名的Chebyshev 不等式，用于估计随机变量偏离其期望的概率。

特别形式

令 a = k\sigma ，其中 \sigma = \sqrt{\mathrm{D}[X]} 是 X 的标准差，则：

P\{ |X - \mathbb{E}X| \ge k\sigma \} \le \frac{1}{k^2}

该形式说明：随机变量超过 k 倍标准差偏离其期望的概率最多为 \frac{1}{k^2} ，随着 k 的增大，这一概率迅速下降。

证明

我们注意到事件 \{ |X - \mathbb{E}[X]| \ge a \} 等价于 \{ (X - \mathbb{E}[X])^2 \ge a^2 \} 。由于 (X - \mathbb{E}[X])^2 \ge 0 ，我们可以直接使用 Markov 不等式：

P\{ |X - \mathbb{E}X| \ge a \} = P\{ (X - \mathbb{E}X)^2 \ge a^2 \} \le \frac{\mathbb{E}[(X - \mathbb{E}X)^2]}{a^2} = \frac{\mathrm{D}X}{a^2}

证毕。

在分析随机化算法时，我们常需要估计某个随机变量远离期望值的概率。Chebyshev 不等式虽然通用，但估计较松，而 Chernoff 不等式 和 Hoeffding 不等式 提供了更紧的界，尤其适用于大量独立试验的和。

Chernoff 不等式

Chernoff 不等式的推导其实是 Markov 不等式的一种应用。设 X 为任意实值随机变量， t > 0 ，则：

P\{ X \ge a \} = P\left\{ e^{tX} \ge e^{ta} \right\} \le \frac{\mathbb{E}[e^{tX}]}{e^{ta}}

类似地，当 t < 0 时，有：

P\{ X \le a \} = P\left\{ e^{tX} \ge e^{ta} \right\} \le \frac{\mathbb{E}[e^{tX}]}{e^{ta}}

这就是 Chernoff 方法的核心思想：将尾部概率转化为指数函数的期望估计。

Poisson 试验之和的 Chernoff Bound（经典应用）

在实际中，我们经常遇到形如“进行 n 次独立试验，每次结果为 0 或 1”的问题。这类模型也被称为Poisson 试验（即伯努利试验）。

一次 Poisson 试验可以用随机变量 X 表示，满足：

P\{X = 1\} = p, \quad P\{X = 0\} = 1 - p

设 X_1, X_2, \dots, X_n 是 n 次相互独立的 Poisson 试验，定义：

X = \sum_{i=1}^n X_i, \quad \mu = \mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[X_i]

则对任意 0 < \epsilon < 1 ，有经典的 Chernoff 不等式：

P\left( |X - \mu| \ge \epsilon \mu \right) \le 2 \exp\left( -\frac{1}{3} \mu \epsilon^2 \right)

它提供了指数级衰减的概率上界。

Hoeffding 不等式

当随机变量不是严格的 0/1（即非伯努利变量），我们可以使用更一般的 Hoeffding 不等式。设 X_1, \dots, X_n 为相互独立的实值随机变量，且每个 X_i 满足：

X_i \in [a_i, b_i]

记总和为：

X = \sum_{i=1}^n X_i, \quad \mu = \mathbb{E}[X]

则对任意 \epsilon > 0 ，有：

P\{ |X - \mu| \ge \epsilon \} \le 2 \exp\left( \frac{-2 \epsilon^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)

该不等式不依赖于具体分布，只要求每个变量落在固定区间内，因此非常通用。

综上所述:

  • Markov 不等式 适用于非负随机变量，可用于粗略估计偏离较大的概率，依赖的信息较少（仅期望值），但结论通常较松。

  • Chebyshev 不等式 基于方差信息，可以更准确地描述随机变量围绕期望的集中程度，适用范围广，尤其在缺乏高阶分布信息时仍可使用。

  • Chernoff 不等式 和 Hoeffding 不等式 都用于控制随机变量偏离期望的概率，且提供指数级下降的上界，但它们适用的场景和假设不同：

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#统计学习 3
决策树
插值方法