精校翻译

本页覆盖 1.pdf 的第 1 章正文、注记和习题翻译。关键证明与 Exercises 1.1-1.19 的完整证明已放入学习笔记页。

目录

第 1 章：分析与概率快速回顾

本章回顾的多数材料都属于基础分析和概率课程内容。如果准备充分，可以略读本章；无论如何，建议做章末习题，尤其是较难的题。

1.1 凸集与凸函数

图 1.1 展示了凸集和凸函数的定义。

凹函数的定义类似，只是上面的不等号方向相反。等价地，$f$ 是凹函数，当且仅当 $-f$ 是凸函数。

1.2 范数与内积

你应该已经熟悉度量、范数和内积的定义。可以先用一分钟检查自己是否记得清楚：证明 (a) 范数是凸函数；(b) 赋范空间的单位球是凸集。 查看学习笔记证明

最常用的 $\mathbb R^n$ 上的范数和内积，是 Euclidean 范数与点积。它们定义为

$$ \|x\|_2 = \left(\sum_{i=1}^n x_i^2\right)^{1/2}, \qquad \langle x,y\rangle = x^{\mathsf T}y = \sum_{i=1}^n x_i y_i. \tag{1.2} $$

Euclidean 范数和点积相容，意义是 $\|x\|_2^2=\langle x,x\rangle$。

更一般地，对任意指数 $p\in[1,\infty]$，可以在 $\mathbb R^n$ 上定义 $\ell^p$ 范数：

$$ \|x\|_p = \left(\sum_{i=1}^n |x_i|^p\right)^{1/p}, \quad p\in[1,\infty), \qquad \|x\|_\infty=\max_{i\le n}|x_i|. $$

Minkowski 不等式说明 $\ell^p$ 范数满足三角不等式：对任意向量 $x,y\in\mathbb R^n$，

$$ \|x+y\|_p\le \|x\|_p+\|y\|_p. $$

因此，对每个 $p\in[1,\infty]$，$\ell^p$ 范数确实在 $\mathbb R^n$ 上定义了一个范数。这里也建议读者自行检查。 查看学习笔记证明

理解 $\ell^p$ 范数几何形状的最好方式，是观察空间 $(\mathbb R^n,\|\cdot\|_p)$ 的单位球：

$$ B_p^n = \{x\in\mathbb R^n:\|x\|_p\le1\}. $$

例如，$B_2^n$ 是通常的 Euclidean 单位球，也就是半径为 $1$ 的圆球；$B_\infty^n$ 是立方体；$B_1^n$ 是 cross-polytope，也就是高维八面体：

$$ B_\infty^n=[-1,1]^n, \qquad B_1^n = \operatorname{conv}\bigl(\{\pm e_1,\ldots,\pm e_n\}\bigr), \tag{1.3} $$

其中 $e_1,\ldots,e_n$ 表示 $\mathbb R^n$ 的标准基。证明见习题 1.6。 查看学习笔记完整证明 图 1.2 展示了不同指数 $p$ 对应的 $\ell^p$ 单位球。

对给定向量 $x$，$\ell^p$ 范数随 $p$ 增大而减小：

$$ \|x\|_q\le \|x\|_p \quad\text{whenever } p\le q. \tag{1.4} $$

证明见习题 1.17。 查看学习笔记完整证明 等价地，$\ell^p$ 单位球随 $p$ 增大而变大：若 $p\le q$，则 $B_p^n\subset B_q^n$。为什么？ 查看学习笔记证明

Hölder 不等式是紧的。在习题 1.19 中，你会检查：对任意向量 $x$，都可以找到一个向量 $y\ne0$，使得 Hölder 不等式取等。换句话说，$\ell^p$ 范数满足下面的对偶公式：

$$ \operatorname*{max}\left\{\langle x,y\rangle:\ y\in B_{p'}^n\right\} = \|x\|_p. \tag{1.6} $$ 查看学习笔记完整证明

1.3 随机变量与随机向量

在基础概率论课程中，我们学过与随机变量 $X$ 相关的两个最重要的量：期望（也叫均值）与方差。它们记为

$$ \mathbb E X, \qquad \operatorname{Var}(X)=\mathbb E(X-\mathbb EX)^2. \tag{1.7} $$

期望的线性性保证：对任意随机变量 $X_1,\ldots,X_n$，不论它们是否独立，并且对任意固定数 $a_1,\ldots,a_n$，都有

$$ \mathbb E\left[a_1X_1+\cdots+a_nX_n\right] = a_1\mathbb EX_1+\cdots+a_n\mathbb EX_n. $$

方差一般不满足类似性质。不过，如果随机变量 $X_i$ 相互独立，甚至只要它们两两不相关，那么

$$ \operatorname{Var}\left(a_1X_1+\cdots+a_nX_n\right) = a_1^2\operatorname{Var}(X_1)+\cdots+a_n^2\operatorname{Var}(X_n). \tag{1.8} $$

最简单的随机变量例子是给定事件 $E$ 的指标，记为 $\mathbf 1_E$。事件 $E$ 发生时，随机变量 $\mathbf 1_E$ 取值 $1$；事件 $E$ 不发生时，它取值 $0$。指标函数的期望显然满足

$$ \mathbb E\mathbf 1_E=\mathbb P(E). \tag{1.9} $$

随机变量 $X$ 的矩母函数定义为

$$ M_X(t)=\mathbb E e^{tX}, \quad t\in\mathbb R. $$

对 $p>0$，$X$ 的 $p$ 阶矩定义为 $\mathbb EX^p$，$p$ 阶绝对矩定义为 $\mathbb E|X|^p$。若对绝对矩取 $p$ 次方根，就得到随机变量的 $L^p$ 范数：

$$ \|X\|_{L^p} = (\mathbb E|X|^p)^{1/p} \quad\text{for }p\in(1,\infty), \qquad \|X\|_{L^\infty} = \operatorname*{ess\,sup}|X|. \tag{1.10} $$

这里 $\operatorname*{ess\,sup}$ 表示本质上确界。

指数 $p=2$ 很特殊：$L^2$ 不只是赋范空间，还是内积空间。它的内积为

$$ \langle X,Y\rangle_{L^2} = \mathbb EXY, \tag{1.11} $$

并且它和 $L^2$ 范数相容，即 $\|X\|_{L^2}^2=\langle X,X\rangle_{L^2}$。

随机变量 $X$ 的标准差是

$$ \sigma(X) = \sqrt{\operatorname{Var}(X)} = \|X-\mathbb EX\|_{L^2}. \tag{1.12} $$

随机变量 $X$ 与 $Y$ 的协方差是

$$ \operatorname{cov}(X,Y) = \mathbb E(X-\mathbb EX)(Y-\mathbb EY) = \langle X-\mathbb EX,\ Y-\mathbb EY\rangle_{L^2}. \tag{1.13} $$

随机变量的概念可以推广到高维。一个取值于 $\mathbb R^n$ 的随机向量 $X=(X_1,\ldots,X_n)$，可以定义为一个 $n$ 个坐标 $X_i$ 全部都是随机变量的向量。$X$ 的期望按坐标定义：

$$ \mathbb EX = (\mathbb EX_1,\ldots,\mathbb EX_n). $$

那么高维中的方差该怎样理解？如果希望传统方差定义 (1.7) 对随机向量也有意义，就必须决定怎样对向量 $x\in\mathbb R^n$ “平方”，或者怎样让向量 $x$ 与自身相乘。这里有两种做法：一种是点积，也就是“内积” $x^{\mathsf T}x=\|x\|_2^2$；另一种是“外积” $xx^{\mathsf T}$。第一种解释会把 $X$ 的方差定义为 $\mathbb E\|X-\mathbb EX\|_2^2$，这个量在 Appetizer 中发挥了重要作用。第二种解释提供的信息更多，它引出了协方差矩阵：

$$ \operatorname{cov}(X) = \mathbb E(X-\mathbb EX)(X-\mathbb EX)^{\mathsf T}. $$

这是一个 $n\times n$ 矩阵，它的第 $(i,j)$ 个元素等于 $\operatorname{cov}(X_i,X_j)$。我们会在第 3.2 节使用协方差矩阵。

1.4 并集界

若 $E_i$ 是两两不交的事件，概率的可加性公理告诉我们

$$ \mathbb P\left(\bigcup_{i=1}^n E_i\right) = \sum_{i=1}^n\mathbb P(E_i). $$

若事件 $E_i$ 并不互斥，这个等式可能失败：属于多个事件 $E_i$ 的样本点在左边只被计数一次，但在右边会被计数多次。因此，我们得到的是一个不等式。

并集界通常用于控制“坏事件”发生的概率。

1.5 条件化

条件化技巧常常帮助我们计算概率和期望。它基于条件概率的概念：给定事件 $F$ 时事件 $E$ 的条件概率记为

$$ \mathbb P(E\mid F) = \frac{\mathbb P(E\cap F)}{\mathbb P(F)}. $$

它也基于条件期望的概念：给定随机变量 $Y$ 时随机变量 $X$ 的条件期望记为 $\mathbb E[X\mid Y]$。

全期望公式说

$$ \mathbb E X = \mathbb E\big[\mathbb E[X\mid Y]\big]. \tag{1.15} $$

非正式地说，为了计算 $X$ 的期望，我们可以先在固定 $Y$ 的取值时对 $X$ 求平均，然后再对 $Y$ 的取值求平均。这就是条件化技巧的核心。

条件化也能帮助我们计算概率。若 $E$ 是事件，$Y$ 是随机变量，则可定义给定 $Y$ 时 $E$ 的条件概率为

$$ \mathbb P(E\mid Y) := \mathbb E[\mathbf 1_E\mid Y], $$

其中 $\mathbf 1_E$ 是事件 $E$ 的指标函数。由于 $\mathbb E\mathbf 1_E=\mathbb P(E)$，全期望公式在这里变成

$$ \mathbb P(E) = \mathbb E\big[\mathbb P(E\mid Y)\big]. \tag{1.16} $$

因此，若要用条件化计算概率，我们可以先在固定 $Y$ 的取值时计算概率，再对 $Y$ 求平均。

设样本空间 $\Omega$ 被分解为互不相交的事件 $F_1,F_2,\ldots$。也就是说，每个样本结果恰好属于其中一个 $F_i$。那么全概率公式允许我们如下计算任意事件 $E$ 的概率：

$$ \mathbb P(E) = \sum_i \mathbb P(E\mid F_i)\mathbb P(F_i). \tag{1.17} $$

全概率公式可以由全期望公式快速推出。为此，在 (1.16) 中令随机变量 $Y$ 在事件 $F_i$ 发生时取值 $i$。注意，随机变量 $\mathbb P(E\mid Y)$ 以概率 $\mathbb P\{Y=i\}=\mathbb P(F_i)$ 取值

$$ \mathbb P(E\mid Y=i)=\mathbb P(E\mid F_i). $$

上面关于随机变量 $X,Y$ 的讨论，对随机向量同样成立。

顺便说一句，Example 1.5.1 的结果是尖锐的。若恰好有两个非零系数 $a_i$，且它们彼此相等，则 $\mathbb P\{S_n=0\}=1/2$。

1.6 概率不等式

Jensen 不等式说，对任意随机变量 $X$ 和凸函数 $f:\mathbb R\to\mathbb R$，都有

$$ f(\mathbb EX) \le \mathbb E f(X). \tag{1.18} $$

更一般地，若随机向量 $X$ 取值于 $\mathbb R^n$，$f:\mathbb R^n\to\mathbb R$ 是凸函数，(1.18) 仍成立。习题 1.3 会要求你对取有限多个值的随机向量证明这一点；一般情形可由逼近推出。 查看学习笔记完整证明 特别地，由于 $\mathbb R^n$ 上任意范数都是凸函数，Jensen 不等式给出

$$ \|\mathbb EX\| \le \mathbb E\|X\|. \tag{1.19} $$

$L^p$ 范数随 $p$ 单调增加：

$$ \|X\|_{L^p} \le \|X\|_{L^q} \quad\text{whenever }p\le q. \tag{1.20} $$

参见习题 1.11。 查看学习笔记完整证明

Minkowski 不等式说，对任意 $p\in[1,\infty]$ 和任意 $X,Y\in L^p$，都有

$$ \|X+Y\|_{L^p} \le \|X\|_{L^p}+\|Y\|_{L^p}. \tag{1.21} $$

换句话说，$L^p$ 范数满足三角不等式。

Cauchy-Schwarz 不等式说，对任意 $X,Y\in L^2$，都有

$$ \|XY\|_{L^1} \le \|X\|_{L^2}\|Y\|_{L^2}. $$

Hölder 不等式把这个结果推广到 $L^p$ 范数。若 $p,p'\in[1,\infty]$ 是一对共轭指数，即 $1/p+1/p'=1$，且 $X\in L^p$、$Y\in L^{p'}$，则

$$ \|XY\|_{L^1} \le \|X\|_{L^p}\|Y\|_{L^{p'}}. \tag{1.22} $$

如基础概率课程中所述，随机变量 $X$ 的分布直观上描述了 $X$ 以什么概率取哪些值。更严格地说，$X$ 的分布由其累积分布函数（CDF）决定：

$$ F_X(t)=\mathbb P\{X\le t\}, \qquad t\in\mathbb R. $$

实际使用中，更方便的往往是随机变量的尾部：

$$ \mathbb P\{X>t\} = 1-F_X(t). $$

下面的结果允许我们用尾部概率计算期望。

反过来，Markov 不等式用期望控制尾部概率。

如果我们只知道 $\mathbb EX$，Markov 不等式给出了可能的最佳尾界。但若还知道方差，就能得到随 $t$ 二次衰减的更好界，从而了解 $X$ 围绕均值的集中程度。

1.7 极限定理

独立随机变量和的研究位于经典概率论的核心。设 $X_1,\ldots,X_N$ 是独立同分布随机变量，均值为 $\mu$，方差为 $\sigma^2$。由和的方差公式 (1.8)，有

$$ \operatorname{Var}\left(\frac1N\sum_{i=1}^N X_i\right) = \frac{\sigma^2}{N}. \tag{1.23} $$

因此，当样本量 $N$ 增大时，样本均值 $\frac1N\sum_{i=1}^N X_i$ 的方差会收缩到 0。这提示我们：当 $N$ 很大时，样本均值应当紧密集中在其期望 $\mu$ 附近。概率论中最重要的结果之一，大数定律，正是严格表述了这一点。

中心极限定理进一步说明：适当缩放后的和 $S_N$ 的极限分布是正态分布，也常称为 Gaussian 分布。

依分布收敛的意思是，$Z_N$ 的累积分布函数逐点收敛到 $g\sim N(0,1)$ 的累积分布函数。用尾概率表示，就是对每个 $t\in\mathbb R$，

$$ \mathbb P\{Z_N>t\} \to \mathbb P\{g>t\} = \frac1{\sqrt{2\pi}}\int_t^\infty e^{-x^2/2}\,dx \quad\text{as }N\to\infty. $$

现在考虑独立随机变量 $X_i\sim\operatorname{Ber}(p_i)$，其中参数 $p_i$ 随 $N\to\infty$ 下降得很快，使得和 $S_N$ 的均值保持在 $O(1)$ 量级，而不是与 $N$ 成正比。在这种情形下，中心极限定理不再适用。下面要陈述的另一个结果说明，$S_N$ 仍会收敛，但极限不再是正态分布，而是 Poisson 分布。

Poisson 分布的概率质量函数 (1.26) 包含阶乘 $k!$，而阶乘并不是一个容易直接处理的函数。当 $k$ 很大时，可以用 Stirling 近似简化它。

在 (1.26) 中使用 Stirling 近似可知，对任意固定参数 $\lambda>0$，若 $Z\sim\operatorname{Pois}(\lambda)$，则当 $k\to\infty$ 时，

$$ \mathbb P\{Z=k\} = \frac{e^{-\lambda}}{\sqrt{2\pi k}} \left(\frac{e\lambda}{k}\right)^k (1+o(1)). \tag{1.27} $$

因此该概率大致按 $k^{-k}$ 衰减，也就是略快于指数衰减。

Stirling 近似也有非渐近版本：它们对每个给定的 $n$ 成立，而不是只在 $n\to\infty$ 的极限中成立。下面是其中一个。

1.8 注记

我们在 Example 1.5.1 中提出的问题，被称为 Littlewood-Offord 问题。这个问题最早由 Littlewood 和 Offord [217] 以及 Erdős [122] 考虑；此后，这个问题及其变体被广泛研究。可参见综述 [318, 291, 258]。

大数强定律（Theorem 1.7.1）和 Lindeberg-Lévy 中心极限定理（Theorem 1.7.3）的证明，可参见例如 [116, Sections 1.7 and 2.4] 与 [42, Sections 6 and 27]。

Proposition 1.6.2 和 Corollary 1.6.3 都归功于 Chebyshev。不过，按照已经形成的传统，我们把 Proposition 1.6.2 称为 Markov 不等式。

用现代语言来说，Example 1.4.2、习题 1.9 和习题 1.10 确定了 Erdős-Rényi 模型 $G(n,p)$ 中存在孤立顶点的阈值。这个问题最早由 Erdős 和 Rényi 的奠基性论文 [121] 研究。关于随机图度数，现在已有更一般、更精确的结果；参见 [47, Chapter 3] 和 [131, Chapter 3]。习题 1.10 展示的二阶矩方法在组合学和理论计算机科学中无处不在；参见 [17, Chapter 4]。习题 1.8 的结果在渐近意义下是最优的：Erdős-Rényi 随机图 $G\sim G(n,p)$ 中最大独立集的基数近似为 $2\log_b n$，其中 $b=1/(1-p)$；参见 [131, Section 7.2]。

Stirling 近似（Lemma 1.7.7）的一个短证明可见 [286] 和 [123, II.9]。该证明给出如下非渐近结果，它对每个 $n\in\mathbb N$ 都成立：

$$ \sqrt{2\pi n}\left(\frac ne\right)^n e^{\frac1{12n+1}} \le n! \le \sqrt{2\pi n}\left(\frac ne\right)^n e^{\frac1{12n}}. $$

这个结果推出 Stirling 近似的渐近形式（Lemma 1.7.8），并且也改进了 Lemma 1.7.8。Gamma 函数 Stirling 近似 (1.31) 的短证明可参见 [44, 101]；非渐近版本可参见 [172]。

Exercises

校对说明

• convex hull 统一译为“凸包”。
• union bound 译为“并集界”，不用“联合界”，以便和后续概率论笔记统一。
• conditioning 译为“条件化”，强调证明策略，而不只是一条条件概率公式。
• non-asymptotic 译为“非渐近”，指结论对固定有限维度和样本量成立。