精校翻译
本页覆盖 1.pdf 的第 1 章正文、注记和习题翻译。关键证明与 Exercises 1.1-1.19 的完整证明已放入学习笔记页。
目录
| 原书部分 | 中文说明 | 页码 | 翻译 | 笔记 |
|---|---|---|---|---|
| Chapter 1 | 分析与概率基础工具的整体回顾。 | PDF p.8 | 译文 | 笔记 |
| 1.1 Convex sets and functions | 凸集、凸函数、最大值原则与 Jensen 不等式。 | PDF p.8 | 译文 | 笔记 |
| 1.2 Norms and inner products | Euclidean 范数、$\ell^p$ 范数、对偶范数与 Hilbert 空间。 | PDF p.8-10 | 译文 | 笔记 |
| 1.3 Random variables and random vectors | 随机变量、分布、独立性、随机向量与常见分布。 | PDF p.10-12 | 译文 | 笔记 |
| 1.4 Union bound | 并集界与高维概率中控制多个坏事件的基本方法。 | PDF p.12-13 | 译文 | 笔记 |
| 1.5 Conditioning | 条件概率、全概率公式、条件期望与条件方差。 | PDF p.13-15 | 译文 | 笔记 |
| 1.6 Probabilistic inequalities | Markov、Chebyshev、Paley-Zygmund 与尾积分公式。 | PDF p.15-17 | 译文 | 笔记 |
| 1.7 Limit theorems | 大数定律、中心极限定理、Poisson 极限定理与 Berry-Esseen。 | PDF p.17-20 | 译文 | 笔记 |
| 1.8 Notes | 原书补充说明与参考文献线索。 | PDF p.20 | 译文 | 笔记 |
| Exercises 1.1-1.19 | 本章基础工具的完整练习翻译。 | PDF p.20-24 | 译文 | 证明 |
第 1 章：分析与概率快速回顾
本章回顾的多数材料都属于基础分析和概率课程内容。如果准备充分，可以略读本章；无论如何，建议做章末习题，尤其是较难的题。
1.1 凸集与凸函数
集合 $K\subset\mathbb R^n$ 称为凸集，是指对 $K$ 中任意一对点，连接这两点的线段仍包含在 $K$ 中；也就是
$$ \lambda x+(1-\lambda)y\in K. $$这里 $x,y\in K$，$\lambda\in[0,1]$。
设 $K\subset\mathbb R^n$ 是凸集。函数 $f:K\to\mathbb R$ 称为凸函数，是指
$$ f(\lambda x+(1-\lambda)y) \le \lambda f(x)+(1-\lambda)f(y), \quad x,y\in K,\ \lambda\in[0,1]. \tag{1.1} $$换句话说，若把 $f$ 限制在 $K$ 中任意两点连成的线段上，$f$ 的图像总在连接这两个端点函数值的线段下方，那么 $f$ 是凸函数。
图 1.1 展示了凸集和凸函数的定义。
凹函数的定义类似，只是上面的不等号方向相反。等价地，$f$ 是凹函数，当且仅当 $-f$ 是凸函数。
最大值原则说：若凸函数定义在凸集 $K=\operatorname{conv}(x_1,\ldots,x_n)$ 上，那么它的最大值会在某个点 $x_i$ 处取得。证明见习题 1.4。
查看学习笔记完整证明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$。为什么？ 查看学习笔记证明
对所有向量 $x,y\in\mathbb R^n$，都有
$$ |\langle x,y\rangle| \le \|x\|_2\|y\|_2. $$Hölder 不等式把 Cauchy-Schwarz 不等式推广到 $\ell^p$ 范数：
$$ |\langle x,y\rangle| \le \|x\|_p\|y\|_{p'} \quad\text{if}\quad \frac1p+\frac1{p'}=1. \tag{1.5} $$满足 (1.5) 中条件的一对数 $p,p'\in[1,\infty]$ 称为共轭指数。
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}$ 表示本质上确界。
给定概率空间上所有具有有限 $L^p$ 范数的随机变量组成的赋范空间，称为 $L^p$ 空间：
$$ L^p=\{X:\|X\|_{L^p}<\infty\}. $$Minkowski 不等式说明，对每个 $p\in[1,\infty]$，$L^p$ 范数确实在 $L^p$ 空间上定义了一个范数。
指数 $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$ 的样本点在左边只被计数一次，但在右边会被计数多次。因此，我们得到的是一个不等式。
对任意事件 $E_1,\ldots,E_n$，都有
$$ \mathbb P\left(\bigcup_{i=1}^n E_i\right) \le \sum_{i=1}^n \mathbb P(E_i). $$ 查看学习笔记完整证明如果事件 $\bigcup_{i=1}^n E_i$ 发生，那么至少有一个事件 $E_i$ 发生。因此指标函数满足
$$ \mathbf 1_{\bigcup_{i=1}^n E_i} \le \sum_{i=1}^n \mathbf 1_{E_i}. \tag{1.14} $$右边计数的是发生了多少个事件 $E_i$。现在对两边取期望，并使用 $\mathbb E\mathbf 1_E=\mathbb P(E)$ 和期望的线性性，即得结论。
并集界通常用于控制“坏事件”发生的概率。
设 $n\ge2$ 名新生来到校园。任意一对学生独立地以概率 $p$ 成为朋友。若
$$ p\ge \frac{4\ln n}{n}, $$则以至少 $1-1/n$ 的概率，每名学生都有至少一个朋友。
查看学习笔记完整证明把学生编号为 $1,\ldots,n$，令 $E_i$ 表示学生 $i$ 没有朋友这一事件。学生 $i$ 没有朋友，意味着其他 $n-1$ 名学生都没有和 $i$ 成为朋友；这些事件独立，且每个概率为 $1-p$。因此
$$ \mathbb P(E_i)=(1-p)^{n-1}. $$我们要控制坏事件
$$ B=\{\text{存在没有朋友的学生}\} = \bigcup_{i=1}^n E_i. $$并集界给出
$$ \mathbb P(B) \le \sum_{i=1}^n\mathbb P(E_i) = n(1-p)^{n-1}. $$用 $1-p\le e^{-p}$，并结合 $n\ge2$ 与 $p\ge 4\ln(n)/n$，得到
$$ n(1-p)^{n-1} \le ne^{-p(n-1)} \le ne^{-2\ln n} = \frac1n. $$所以坏事件的补集，也就是“没有孤立学生”这一事件，发生概率至少为 $1-1/n$。
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$ 的讨论，对随机向量同样成立。
设 $a_1,\ldots,a_n$ 是实数，且不全为零。若符号随机选取，那么
$$ \pm a_1\pm\cdots\pm a_n=0 $$的概率是多少？我们将说明，这个概率总是不超过 $1/2$。
严格地说，把随机符号建模为独立 Rademacher 随机变量 $X_1,\ldots,X_n$，即每个 $X_i$ 以概率 $1/2$ 取 $-1$ 和 $1$。我们断言
$$ \mathbb P\{S_n=0\}\le\frac12, \qquad S_n=\sum_{i=1}^n a_iX_i. $$ 查看学习笔记完整证明重新排列下标后，不妨设 $a_n\ne0$。证明思路是：暴露和式的最后一项 $a_nX_n$，同时通过条件化固定前面的所有项。
条件化在随机向量 $(X_1,\ldots,X_{n-1})$ 上。这样就固定了 $X_1,\ldots,X_{n-1}$ 的取值，因此也固定了
$$ S_{n-1}=\sum_{i=1}^{n-1}a_iX_i. $$此时所有剩余随机性都在 $X_n$ 上。由于 $S_n=S_{n-1}+a_nX_n$，有
$$ \mathbb P\{S_n=0\mid X_1,\ldots,X_{n-1}\} = \mathbb P\left\{ X_n=-\frac{S_{n-1}}{a_n} \ \middle|\ X_1,\ldots,X_{n-1} \right\} \le \frac12. $$上面的不等式成立，是因为 $X_n$ 与 $X_1,\ldots,X_{n-1}$ 独立；条件化后 $u=-S_{n-1}/a_n$ 是固定实数；而 Rademacher 分布满足对任意固定 $u\in\mathbb R$，$\mathbb P\{X_n=u\}\le1/2$。
最后使用全期望公式 (1.16)：
$$ \mathbb P\{S_n=0\} = \mathbb E\left[ \mathbb P\{S_n=0\mid X_1,\ldots,X_{n-1}\} \right] \le \mathbb E\frac12 = \frac12. $$顺便说一句，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). $$
下面的结果允许我们用尾部概率计算期望。
任意非负随机变量 $X$ 都满足
$$ \mathbb EX = \int_0^\infty \mathbb P\{X>t\}\,dt. $$该等式两侧要么同时有限，要么同时无限。
查看学习笔记完整证明任意非负实数 $x$ 都可表示为
$$ x = \int_0^x 1\,dt = \int_0^\infty \mathbf 1_{\{t<x\}}\,dt. $$把 $x$ 替换为随机变量 $X$，并对两边取期望，得到
$$ \mathbb EX = \mathbb E\int_0^\infty \mathbf 1_{\{t<X\}}\,dt = \int_0^\infty \mathbb E\mathbf 1_{\{t<X\}}\,dt = \int_0^\infty \mathbb P\{t<X\}\,dt. $$第二个等号中交换期望与积分使用了 Fubini-Tonelli 定理。
反过来，Markov 不等式用期望控制尾部概率。
对任意非负随机变量 $X$ 和任意 $t>0$，都有
$$ \mathbb P\{X\ge t\} \le \frac{\mathbb EX}{t}. $$ 查看学习笔记完整证明固定 $t>0$。任意实数 $x$ 都可写成
$$ x = x\mathbf 1_{\{x\ge t\}} + x\mathbf 1_{\{x<t\}}. $$把 $x$ 替换为非负随机变量 $X$，并取期望：
$$ \mathbb EX = \mathbb E X\mathbf 1_{\{X\ge t\}} + \mathbb E X\mathbf 1_{\{X<t\}} \ge \mathbb E\,t\mathbf 1_{\{X\ge t\}}+0 = t\cdot\mathbb P\{X\ge t\}. $$两边同除以 $t$ 即得结论。
如果我们只知道 $\mathbb EX$，Markov 不等式给出了可能的最佳尾界。但若还知道方差，就能得到随 $t$ 二次衰减的更好界，从而了解 $X$ 围绕均值的集中程度。
设随机变量 $X$ 的均值为 $\mu$，方差为 $\sigma^2$。则对任意 $t>0$，
$$ \mathbb P\{|X-\mu|\ge t\} \le \frac{\sigma^2}{t^2}. $$ 查看学习笔记完整证明将事件 $|X-\mu|\ge t$ 两边平方，并对非负随机变量 $(X-\mu)^2$ 使用 Markov 不等式：
$$ \mathbb P\{|X-\mu|\ge t\} = \mathbb P\{(X-\mu)^2\ge t^2\} \le \frac{\mathbb E(X-\mu)^2}{t^2} = \frac{\sigma^2}{t^2}. $$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$ 附近。概率论中最重要的结果之一，大数定律，正是严格表述了这一点。
设 $X_1,X_2,\ldots$ 是一列独立同分布随机变量，均值为 $\mu$。令
$$ S_N=X_1+\cdots+X_N. $$则当 $N\to\infty$ 时，
$$ \frac{S_N}{N}\to\mu \quad\text{almost surely}. $$中心极限定理进一步说明：适当缩放后的和 $S_N$ 的极限分布是正态分布，也常称为 Gaussian 分布。
随机变量 $X$ 称为标准正态随机变量，记作
$$ X\sim N(0,1), $$如果 $X$ 的密度为
$$ f(x) = \frac1{\sqrt{2\pi}}e^{-x^2/2}, \qquad x\in\mathbb R. \tag{1.24} $$此时 $X$ 的均值为 0，方差为 1。
更一般地，随机变量 $X$ 服从正态分布
$$ X\sim N(\mu,\sigma^2) $$是指 $X$ 可以写成 $X=\mu+\sigma Z$，其中 $\mu\in\mathbb R$、$\sigma>0$ 为固定数，且 $Z\sim N(0,1)$。此时 $X$ 的密度为
$$ f(x) = \frac1{\sigma\sqrt{2\pi}} \exp\left( -\frac{(x-\mu)^2}{2\sigma^2} \right), \qquad x\in\mathbb R. $$随机变量 $X$ 的均值为 $\mu$，方差为 $\sigma^2$。
设 $X_1,X_2,\ldots$ 是一列独立同分布随机变量，均值为 $\mu$，方差为 $\sigma^2$。令
$$ S_N=X_1+\cdots+X_N, $$并将其标准化为均值为 0、方差为 1 的随机变量：
$$ Z_N := \frac{S_N-\mathbb ES_N}{\sqrt{\operatorname{Var}(S_N)}} = \frac1{\sigma\sqrt N}\sum_{i=1}^N(X_i-\mu). $$则当 $N\to\infty$ 时，
$$ Z_N\to N(0,1) \quad\text{in distribution}. $$依分布收敛的意思是，$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$ 是参数为 $p\in(0,1)$ 的 Bernoulli 随机变量，记作
$$ X_i\sim\operatorname{Ber}(p). $$这表示 $X_i$ 以概率 $p$ 取值 1，以概率 $1-p$ 取值 0。容易检查
$$ \mathbb EX_i=p, \qquad \operatorname{Var}(X_i)=p(1-p). $$ 查看学习笔记证明独立 $\operatorname{Ber}(p)$ 随机变量之和
$$ S_N:=X_1+\cdots+X_N $$称为服从二项分布，记作
$$ S_N\sim\operatorname{Binom}(N,p). $$中心极限定理给出，当 $N\to\infty$ 时，
$$ \frac{S_N-Np}{\sqrt{Np(1-p)}} \to N(0,1) \quad\text{in distribution}. \tag{1.25} $$中心极限定理的这个特例称为 de Moivre-Laplace 定理。
现在考虑独立随机变量 $X_i\sim\operatorname{Ber}(p_i)$，其中参数 $p_i$ 随 $N\to\infty$ 下降得很快，使得和 $S_N$ 的均值保持在 $O(1)$ 量级，而不是与 $N$ 成正比。在这种情形下，中心极限定理不再适用。下面要陈述的另一个结果说明，$S_N$ 仍会收敛，但极限不再是正态分布，而是 Poisson 分布。
若随机变量 $Z$ 取值于 $\{0,1,2,\ldots\}$，并满足
$$ \mathbb P\{Z=k\} = e^{-\lambda}\frac{\lambda^k}{k!}, \qquad k=0,1,2,\ldots, \tag{1.26} $$则称 $Z$ 服从参数为 $\lambda>0$ 的 Poisson 分布，记作
$$ Z\sim\operatorname{Pois}(\lambda). $$设 $X_{N,i}\sim\operatorname{Ber}(p_{N,i})$ 相互独立，其中 $N=1,2,\ldots$，$1\le i\le N$。令
$$ S_N=X_{N,1}+\cdots+X_{N,N}. $$若当 $N\to\infty$ 时，
$$ \max_{i\le N}p_{N,i}\to0 \quad\text{and}\quad \mathbb ES_N=p_{N,1}+\cdots+p_{N,N}\to\lambda<\infty, $$则当 $N\to\infty$ 时，
$$ S_N\to\operatorname{Pois}(\lambda) \quad\text{in distribution}. $$Poisson 分布的概率质量函数 (1.26) 包含阶乘 $k!$，而阶乘并不是一个容易直接处理的函数。当 $k$ 很大时，可以用 Stirling 近似简化它。
当 $n\to\infty$ 时，
$$ n! = \sqrt{2\pi n} \left(\frac ne\right)^n (1+o(1)). $$在 (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$ 的极限中成立。下面是其中一个。
对任意 $n\in\mathbb N$，都有
$$ \left(\frac ne\right)^n \le n! \le en\left(\frac ne\right)^n. \tag{1.28} $$ 查看学习笔记完整证明回忆 $e^x$ 的 Taylor 级数，只保留第 $n$ 项，可得
$$ e^x\ge \frac{x^n}{n!}. $$取 $x=n$ 并整理，即得 (1.28) 的下界。
为了证明上界，注意到
$$ \ln(n!) = \sum_{k=1}^n\ln k \le \int_1^n\ln x\,dx+\ln n = n(\ln n-1)+1+\ln n. \tag{1.29} $$(1.29) 中的不等式来自与积分判别法相同的面积比较。对两边取指数并整理，即得 (1.28) 的上界。
Gamma 函数把阶乘概念推广到所有实数，甚至推广到实部为正的复数。它定义为
$$ \Gamma(z) := \int_0^\infty t^{z-1}e^{-t}\,dt. \tag{1.30} $$反复分部积分可得
$$ \Gamma(n+1)=n!, \qquad n=0,1,2,\ldots. $$Stirling 近似也适用于 Gamma 函数：
$$ \Gamma(z+1) = \sqrt{2\pi z} \left(\frac ze\right)^z (1+o(1)) \quad\text{as }\mathbb R\ni z\to\infty. \tag{1.31} $$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
任取子集 $T\subset\mathbb R^n$。检查 $\operatorname{conv}(T)$ 是凸集。
查看学习笔记完整证明检查有限多个凸函数的逐点最大值仍然是凸函数。
查看学习笔记完整证明(a) 凸函数的定义 (1.1) 涉及两个点 $x$ 和 $y$ 的凸组合。现在把它推广到任意有限多个点。设 $K\subset\mathbb R^n$ 是凸集。证明函数 $f:K\to\mathbb R$ 是凸函数，当且仅当下面性质成立：对任意 $m\in\mathbb N$、任意向量 $x_i\in K$，以及任意满足 $\lambda_i\ge0$ 且 $\sum_{i=1}^m\lambda_i=1$ 的数 $\lambda_i$，都有
$$ f\left(\sum_{i=1}^m \lambda_i x_i\right) \le \sum_{i=1}^m \lambda_i f(x_i). $$(b) 设 $X$ 是取有限多个值的 $\mathbb R^n$ 随机向量，且 $f:\mathbb R^n\to\mathbb R$ 是凸函数。由 (a) 推出 Jensen 不等式：
$$ f(\mathbb EX)\le \mathbb E f(X). $$ 查看学习笔记完整证明证明：对任意凸函数 $f$ 和任意子集 $T\subset\mathbb R^n$，都有
$$ \operatorname*{sup}_{x\in\operatorname{conv}(T)} f(x) = \operatorname*{sup}_{x\in T} f(x). $$ 查看学习笔记完整证明立方体是它所有顶点的凸包，这看起来几乎是显然的：
$$ [-1,1]^n = \operatorname{conv}\bigl(\{-1,1\}^n\bigr). $$请通过把立方体中的任意点表示为顶点的凸组合来证明这一点。
查看学习笔记完整证明检查 $\mathbb R^n$ 中 $\ell^1$ 范数对应的单位球，是标准基 $e_1,\ldots,e_n$ 的绝对凸包；也就是
$$ B_1^n = \operatorname{conv}\bigl(\{\pm e_1,\ldots,\pm e_n\}\bigr). $$写出一个公式，把任意点 $x\in B_1^n$ 表示为向量 $\pm e_1,\ldots,\pm e_n$ 的凸组合。
查看学习笔记完整证明假设在 Example 1.4.2 中，到达校园的新生人数 $n$ 本身是一个均值为 $\lambda$ 的 Poisson 随机变量。和前面一样，每一对学生独立地以概率 $p$ 成为朋友。证明：如果 $p\ge 2\ln(\lambda)/\lambda$，那么不存在没有朋友的学生这一事件的概率至少为 $1-1/\lambda$。
查看学习笔记完整证明如果一群人中任意两个人都不是朋友，就称这个群体是独立的。假设 $n\ge7$ 名学生选修高维概率课程，每一对学生独立地以概率 $1/2$ 成为朋友。证明：以至少 $1-1/n$ 的概率，这个班级不存在大小超过 $2\log_2 n$ 的独立子集。
查看学习笔记完整证明现在细化 Example 1.4.2 的结果。设 $n$ 名新生到达校园，每一对学生独立地以概率 $p_n$ 成为朋友。固定任意 $\varepsilon>0$，并假设
$$ p_n>\frac{(1+\varepsilon)\ln n}{n} \quad\text{for every } n\in\mathbb N. $$证明：当 $n\to\infty$ 时，不存在没有朋友的学生这一事件的概率收敛到 $1$。
查看学习笔记完整证明现在证明 Exercise 1.9 的逆向结果。固定任意 $\varepsilon>0$，并假设
$$ p_n<\frac{(1-\varepsilon)\ln n}{n} \quad\text{for every } n\in\mathbb N. $$那么，当 $n\to\infty$ 时，至少存在一名没有朋友的学生这一事件的概率收敛到 $1$。你将使用所谓的二阶矩方法证明这个结果。
(a) 令没有朋友的学生人数为 $S_n$，并把它表示为 $S_n=X_1+\cdots+X_n$，其中 $X_i$ 是“学生 $i$ 没有朋友”这一事件的指标。证明
$$ \mu_n=\mathbb E S_n\to\infty. $$因此，没有朋友的学生的期望人数很大。但这并不会自动推出以高概率至少存在一名没有朋友的学生。为什么？
(b) 通过展开平方来计算二阶矩 $\mathbb E S_n^2$。推出
$$ \frac{\operatorname{Var}(S_n)}{\mu_n^2}\to0. $$(c) 使用 Chebyshev 不等式完成证明。
查看学习笔记完整证明(a) 设 $X$ 是随机变量。证明 $\|X\|_{L^p}$ 是关于 $p$ 的递增函数：
$$ \|X\|_{L^p} \le \|X\|_{L^q} \quad\text{for any }0\le p\le q\le\infty. $$(b) 说明 (a) 中的不等式一般不能反向：对任意 $0\le p<q\le\infty$，找出一个随机变量 $X$，使得 $\|X\|_{L^p}<\infty$ 但 $\|X\|_{L^q}=\infty$。
查看学习笔记完整证明我们知道任意随机变量 $X$ 的 $L^p$ 范数都可以由 $L^\infty$ 范数控制。如果还知道 $X$ 的 $L^1$ 范数很小，就能得到更好的界。证明：
$$ \|X\|_{L^p} \le \|X\|_{L^1}^{1/p} \|X\|_{L^\infty}^{1-1/p} \quad\text{for any }1<p<\infty. $$ 查看学习笔记完整证明设 $X_1,\ldots,X_n$ 是非负随机变量。
(a) 证明
$$ \operatorname*{max}_{i\le n}\mathbb EX_i \le \mathbb E\operatorname*{max}_{i\le n}X_i \le n\cdot\operatorname*{max}_{i\le n}\mathbb EX_i. $$(b) 说明 (a) 中两个不等式都可能达到最优。具体地，找出随机变量 $X_1,\ldots,X_n$ 使得
$$ \operatorname*{max}_{i}\mathbb EX_i = \mathbb E\operatorname*{max}_{i}X_i >0, $$并找出随机变量 $Y_i$ 使得
$$ \mathbb E\operatorname*{max}_{i}Y_i = n\cdot\operatorname*{max}_{i}\mathbb EY_i >0. $$(c) 说明即使对独立随机变量，(a) 中的上界也可以近似最优。具体地，找出独立随机变量 $X_1,\ldots,X_n$，使得
$$ \mathbb E\operatorname*{max}_{i}X_i > c n\cdot \operatorname*{max}_{i}\mathbb EX_i, $$其中 $c>0$ 是绝对常数。
查看学习笔记完整证明设 $X_1,\ldots,X_n$ 是非负随机变量。证明：对任意 $1\le p<\infty$，都有
$$ \left(\sum_{i=1}^n(\mathbb EX_i)^p\right)^{1/p} \le \mathbb E\left(\sum_{i=1}^n X_i^p\right)^{1/p} \le \left(\sum_{i=1}^n\mathbb E(X_i^p)\right)^{1/p}. $$ 查看学习笔记完整证明证明 Lemma 1.6.1 的下面这些更一般版本。
(a) 设 $X$ 是任意随机变量，不要求非负。那么
$$ \mathbb EX = \int_0^\infty \mathbb P\{X>t\}\,dt - \int_{-\infty}^0 \mathbb P\{X<t\}\,dt. $$(b) 设 $X$ 是非负随机变量。设 $f:\mathbb R^+\to\mathbb R^+$ 是递增、可微函数，并满足 $f(0)=0$。那么
$$ \mathbb E f(X) = \int_0^\infty \mathbb P\{X>t\} f'(t)\,dt. $$(c) 设 $X$ 是任意随机变量，不要求非负。推出：对每个 $p\in(0,\infty)$，都有
$$ \mathbb E|X|^p = \int_0^\infty \mathbb P\{|X|>t\}\,p t^{p-1}\,dt. $$ 查看学习笔记完整证明Markov 不等式说，一个随机变量不太可能远大于它的期望。那么反过来呢？一个非负随机变量是否可能以很高概率远小于它的期望？一般来说可以（请想一个例子），但如果二阶矩不太大，就不能这样。设 $X$ 是具有有限方差的非负随机变量。证明：对任意 $\varepsilon\in[0,1]$，都有
$$ \mathbb P\{X>\varepsilon\mathbb EX\} \ge (1-\varepsilon)^2 \frac{(\mathbb EX)^2}{\mathbb E[X^2]}. $$ 查看学习笔记完整证明设 $0\le p\le q\le\infty$。
(a) 证明：对任意向量 $x\in\mathbb R^n$，都有
$$ \|x\|_q \le \|x\|_p \le n^{\frac1p-\frac1q}\|x\|_q. $$(b) 说明 (a) 中两个不等式都可能达到最优。具体地，找出非零向量 $x,y\in\mathbb R^n$，使得 $\|x\|_p=\|x\|_q$，且 $\|y\|_p=n^{\frac1p-\frac1q}\|y\|_q$。
查看学习笔记完整证明任取向量 $x\in\mathbb R^n$。
(a) 证明
$$ \|x\|_p\to\|x\|_\infty \quad\text{as }p\to\infty. $$(b) 事实上，$p$ 不需要太大，$\ell^p$ 范数就已经能相当接近 $\ell^\infty$ 范数。证明：如果 $p\ge\ln n$，则
$$ \|x\|_\infty \le \|x\|_p \le e\|x\|_\infty. $$ 查看学习笔记完整证明设 $p,p'\in[1,\infty]$ 是共轭指数。
(a) 说明 Hölder 不等式是紧的：对任意向量 $x$，都存在向量 $y\ne0$，使得
$$ \langle x,y\rangle = \|x\|_p\|y\|_{p'}. $$(b) 推出：对每个向量 $x\in\mathbb R^n$，都有
$$ \operatorname*{max}\left\{\langle x,y\rangle:\ y\in B_{p'}^n\right\} = \|x\|_p. $$ 查看学习笔记完整证明校对说明
convex hull统一译为“凸包”。union bound译为“并集界”，不用“联合界”，以便和后续概率论笔记统一。conditioning译为“条件化”，强调证明策略，而不只是一条条件概率公式。non-asymptotic译为“非渐近”，指结论对固定有限维度和样本量成立。