开胃篇：用概率覆盖一个集合
我们先从一个优雅的例子开始：概率推理如何帮助我们处理几何问题。如果你更想直接进入正文，可以跳过这一节。
设 $z_1,\ldots,z_m\in\mathbb R^n$。这些点的一个凸组合，是指形如
$$ \sum_{i=1}^m \lambda_i z_i, \qquad \lambda_i\ge 0,\qquad \sum_{i=1}^m\lambda_i=1 \tag{0.1} $$
的线性组合。集合 $T\subset\mathbb R^n$ 的凸包，是 $T$ 中任意有限多个点的所有凸组合构成的集合：
$$ \operatorname{conv}(T) := \left\{ \text{由 }z_1,\ldots,z_m\in T\text{ 构成的凸组合，其中 }m\in\mathbb N \right\}. $$
图 0.1 给出一个直观示例。
在 $\mathbb R^n$ 中，定义一个凸组合所需的点数 $m$ 原本没有先验限制。不过经典的 Caratheodory 定理说明，总可以把点数限制到 $n+1$ 以内。
集合 $T\subset\mathbb R^n$ 的凸包中的每个点，都可以表示为 $T$ 中至多 $n+1$ 个点的凸组合。
这个 $n+1$ 的界是紧的。例如，对一个单纯形来说，确实需要一般位置上的 $n+1$ 个点。可是，如果我们只要求近似表示，而不要求精确表示，会发生什么？答案是：我们可以使用少得多的点，而且所需点数甚至不依赖维度。
设 $T\subset\mathbb R^n$ 包含在欧几里得单位球中。那么，对任意 $x\in\operatorname{conv}(T)$ 和任意 $k\in\mathbb N$，都可以找到 $x_1,\ldots,x_k\in T$，使得
$$ \left\|x-\frac1k\sum_{j=1}^k x_j\right\|_2 \le \frac1{\sqrt k}. $$这个结论有两个令人意外的地方。第一，点数 $k$ 不依赖维度 $n$。第二，所有凸权重都是相等的，都是 $1/k$。当然，允许 $x_j$ 之间有重复。
这个论证称为 B. Maurey 的经验方法。
固定 $x\in\operatorname{conv}(T)$，并把它写成 $z_1,\ldots,z_m\in T$ 的一个凸组合，如 (0.1) 所示：
$$ x=\sum_{i=1}^m\lambda_i z_i. $$让我们用概率方式解释 (0.1)。定义一个随机向量 $Z$，它以概率 $\lambda_i$ 取值 $z_i$：
$$ \mathbb P\{Z=z_i\}=\lambda_i,\qquad i=1,\ldots,m. $$这是可行的，因为系数 $\lambda_i$ 非负且和为 1，所以它们可以被解释为概率。$Z$ 的期望为
$$ \mathbb E Z = \sum_{i=1}^m\lambda_i z_i =x. $$考虑 $Z$ 的独立副本 $Z_1,Z_2,\ldots$，也就是与 $Z$ 同分布且相互独立的随机向量。强大数定律告诉我们
$$ \frac1k\sum_{j=1}^k Z_j\to x \qquad\text{当 } k\to\infty \text{ 时几乎必然成立。} $$为了得到更定量的结果，我们计算均方误差：
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^k Z_j\right\|_2^2 = \frac1{k^2} \mathbb E\left\|\sum_{j=1}^k (Z_j-x)\right\|_2^2 = \frac1{k^2} \sum_{j=1}^k \mathbb E\|Z_j-x\|_2^2. $$最后一个恒等式只是“独立随机变量之和的方差等于方差之和”这一事实的高维版本；请在习题 0.3 中检查它。
还需要控制各项的方差。我们有
$$ \begin{aligned} \mathbb E\|Z_j-x\|_2^2 &=\mathbb E\|Z-\mathbb E Z\|_2^2\\ &=\mathbb E\|Z\|_2^2-\|\mathbb E Z\|_2^2 \qquad\text{（由另一个方差恒等式，见习题 0.1(a)）}\\ &\le \mathbb E\|Z\|_2^2 \le 1 \qquad\text{（因为 }Z\in T\text{，且由对 }T\text{ 的假设可知）。} \end{aligned} $$我们证明了
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^k Z_j\right\|_2^2 \le \frac1k. $$因此，随机变量 $Z_1,\ldots,Z_k$ 存在一个实现，使得
$$ \left\|x-\frac1k\sum_{j=1}^k Z_j\right\|_2^2 \le \frac1k. $$由于按构造每个随机变量 $Z_j$ 都取值于 $T$，证明完成。
0.0.1 覆盖几何集合
定理 0.0.2 可以用来覆盖高维中的多面体。设 $P\subset\mathbb R^n$ 是一个给定集合。要用指定半径的球覆盖 $P$，寻找最少球数通常并不容易。图 0.2 中，六个球可以覆盖这个多边形；但五个球不够用是否显然？
近似 Caratheodory 定理可以帮助我们为高维中的多胞体（polytopes）找到经济的覆盖。
设 $P\subset\mathbb R^n$ 是一个有 $N$ 个顶点、并包含在欧几里得单位球中的多胞体。那么对每个 $k\in\mathbb N$，$P$ 可以由至多 $N^k$ 个半径为 $1/\sqrt k$ 的欧几里得球覆盖。
考虑集合
$$ \mathcal N = \left\{ \frac1k\sum_{j=1}^k x_j: x_j\text{ 是 }P\text{ 的顶点} \right\}. $$我们声称，以 $\mathcal N$ 中的点为中心、半径为 $1/\sqrt k$ 的球族满足推论的结论。为验证这一点，注意到 $P\subset\operatorname{conv}(P)=\operatorname{conv}(T)$，其中 $T=\{P\text{ 的顶点}\}$。因此可将定理 0.0.2 应用于任意 $x\in P\subset\operatorname{conv}(T)$，并推出 $x$ 距离 $\mathcal N$ 中的某个点不超过 $1/\sqrt k$。这说明以 $\mathcal N$ 为中心、半径为 $1/\sqrt k$ 的球确实覆盖 $P$。
为估计 $\mathcal N$ 的基数，注意从 $N$ 个顶点中选取 $k$ 个点并允许重复，共有 $N^k$ 种方式。因此 $|\mathcal N|\le N^k$。证明完成。
覆盖技术在许多场景中都有用。第 4.2 节会把覆盖和填充（packing）联系起来，第 4.3 节会把它和熵、编码联系起来，第 7-8 章还会把它用于随机过程。现在，我们先说明如何用覆盖来研究体积。
你可能记得一些特殊形状的体积公式，例如平行多面体或棱柱。但一般多胞体的体积并不容易计算，尤其是在高维空间中。尽管如此，我们有一个简单的上界。
设 $P$ 是一个有 $N$ 个顶点的多胞体，并且包含在 $\mathbb R^n$ 的欧几里得单位球 $B$ 中。那么
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(3\sqrt{\frac{\log N}{n}}\right)^n. \tag{0.2} $$推论 0.0.3 说明，多胞体 $P$ 可以由至多 $N^k$ 个半径为 $1/\sqrt k$ 的球覆盖。每个这样的球的体积是 $(1/\sqrt k)^n\operatorname{Vol}(B)$。这是因为在 $n$ 维空间中，若把球的半径放大 $r$ 倍，体积会放大 $r^n$ 倍。
$P$ 的体积不超过覆盖它的这些球的总体积，所以
$$ \operatorname{Vol}(P) \le N^k\left(\frac1{\sqrt k}\right)^n\operatorname{Vol}(B). $$整理得到
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \frac{N^k}{k^{n/2}}. \tag{0.3} $$这个界对每个 $k\in\mathbb N$ 都成立。于是让我们找到最优的 $k$，也就是使右侧最小的那个 $k$。为此，对右侧取对数、求导并令导数为零，可得最优值
$$ k_0=\frac{n}{2\log N}. \tag{0.4} $$（请检查！）把 $k=k_0$ 代入 (0.3)，化简表达式，就得到
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(\sqrt{\frac{2e\log N}{n}}\right)^n. $$这个界甚至比我们声称的更好。不过，我们的证明有一个小小的不准确之处。你能在继续读下去之前发现它吗？
$k$ 的值需要是整数，但无法保证最优值 (0.4) 是整数。为修正这个不准确之处，可以取 $k=\lceil k_0\rceil$。把这个 $k$ 代回 (0.3)，并使用 $k_0\le k\le k_0+1$，得到修正后的界
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \frac{N^{k_0+1}}{k_0^{n/2}} \le N\left(\sqrt{\frac{2e\log N}{n}}\right)^n. $$若 $N\le e^{n/9}$，则右侧可由 $\left(3\sqrt{\log(N)/n}\right)^n$ 控制，证明完成。（请检查！）另一方面，若 $N>e^{n/9}$，则 (0.2) 右侧大于 1；由于 $P\subset B$，这样的界显然成立。因此无论哪种情况，证明都完成了。
定理 0.0.4 给出一个反直觉结论：顶点数量适中的多胞体体积极小。如果回忆证明开头关于体积缩放的讨论，可以把界 (0.2) 理解为：$P$ 的体积至多相当于半径为 $3\sqrt{\log(N)/n}$ 的欧几里得球的体积，甚至可能更小。因此，如果 $N$ 的增长慢于 $n$ 的指数函数，这个半径会收缩到 0，意味着 $P$ 只占单位球的极小一部分。
本书中还会遇到其他类似的高维惊讶。随着你对高维空间的直觉逐渐增长，这些现象会开始变得自然。
现在轮到你了：请验证定理 0.0.2 证明中用到的方差公式（习题 0.1、0.3），自己给出一个确定性结果的概率证明（习题 0.4），说明近似 Caratheodory 定理的界基本是紧的（习题 0.5），检查一个非常有用的二项式和估计（习题 0.6，不要跳过），发现另一个高维反直觉现象（习题 0.7-0.8），并改进多胞体的体积上界（习题 0.9）。
注记
本节展示了概率方法：用随机性构造一个有用对象。书籍 [17] 给出了概率方法的许多例子，主要来自组合数学。
本节使用的 B. Maurey 经验方法最早发表于 [271]，此后出现了许多应用。B. Carl 曾用它得到覆盖数的界 [76]，正如我们在推论 0.0.3 中所做的那样。
近似 Caratheodory 定理（定理 0.0.2）有一个较弱版本：不要求凸组合中所有权重相等。即使这个较弱版本也并不平凡。它可以不用概率方法证明，而是使用 Frank-Wolfe 算法的一种形式；这是一种确定性的、迭代式的贪婪算法。可参见 [43，引理 2.6]。
与 Caratheodory 定理类似，组合几何中的若干其他结果也可以通过允许“近似”而非“精确”来变成维度无关的形式 [10]。
定理 0.0.4 及其在习题 0.9 中的加强最早由 B. Carl 和 A. Pajor [77] 证明。通过考虑随机多胞体（random polytopes），N. Dafnis、A. Giannopoulos 和 A. Tsolomitis [90] 证明，习题 0.9 中的界在整个有趣范围 $n\le N\le e^n$ 内都是最优的。
习题
(a) 回忆随机变量 $X$ 的方差满足
$$ \operatorname{Var}(X) = \mathbb{E}(X-\mathbb{E}X)^2 = \mathbb{E}X^2-(\mathbb{E}X)^2. $$我们来证明这个恒等式的高维版本。检查任意随机向量 $Z\in\mathbb{R}^n$ 都满足
$$ \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 = \mathbb{E}\|Z\|_2^2-\|\mathbb{E}Z\|_2^2. $$(b) 设 $Z$ 是 $\mathbb{R}^n$ 中的随机向量，$Z'$ 是 $Z$ 的一个独立副本，即 $Z'$ 与 $Z$ 独立且同分布。检查：
$$ \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 = \frac12\mathbb{E}\|Z-Z'\|_2^2. $$随机变量 $X$ 的方差有下面的极值性质：
$$ \operatorname{Var}(X) = \min_{a\in\mathbb{R}}\mathbb{E}(X-a)^2. $$我们来证明这个事实的更一般的高维版本。检查：若随机向量 $Z\in\mathbb{R}^n$ 满足 $\mathbb{E}\|Z\|_2^2<\infty$，则
$$ \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 = \min_{a\in\mathbb{R}^n}\mathbb{E}\|Z-a\|_2^2. $$回忆：独立随机变量之和的方差等于方差之和。现在证明这个恒等式的高维版本。检查：任意独立、均值为零的随机向量 $Z_1,\ldots,Z_k\in\mathbb{R}^n$ 都满足
$$ \mathbb{E}\biggl\|\sum_{j=1}^k Z_j\biggr\|_2^2 = \sum_{j=1}^k \mathbb{E}\|Z_j\|_2^2. $$设 $x_1,\ldots,x_n$ 是 $\mathbb{R}^n$ 中的向量，且都落在以原点为中心的欧几里得单位球内。
(a) 证明：可以给每个向量指定一个符号 $\varepsilon_i\in\{-1,1\}$，使得
$$ \sum_{i=1}^n \varepsilon_i x_i $$落在以原点为中心、半径为 $\sqrt n$ 的欧几里得球内。
(b) 解释为什么一般不能把 $\sqrt n$ 这个值再降低。
通过例子说明定理 0.0.2 中的界几乎是紧的。具体地，对每个 $n$，找到一个集合 $T\subset\mathbb{R}^n$ 和一个点 $x\in\operatorname{conv}(T)$，使得对 $T$ 中任意 $k$ 个点 $x_1,\ldots,x_k$ 的任意凸组合 $\sum_{j=1}^k\lambda_jx_j$，都有
校勘：原文题干在公式中使用了 $x$，但前文没有显式说明 $x$ 的来源；这里按题意补为“和一个点 $x\in\operatorname{conv}(T)$”。
$$ \biggl\| x-\sum_{j=1}^k\lambda_jx_j \biggr\|_2 \ge \sqrt{\frac1k-\frac1n}. $$固定 $k$ 并令 $n\to\infty$，即可看出定理 0.0.2 在高维中是渐近紧的。
证明：对任意整数 $1\le k\le n$，都有
$$ \left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \sum_{j=0}^k \binom{n}{j} \le \left(\frac{en}{k}\right)^k. $$我们来证明一个反直觉事实：高维球的大部分体积都靠近表面。考虑 $\mathbb{R}^n$ 的欧几里得单位球中那些距离球面不超过 $5/n$ 的点；见图 0.3。证明：这些点占单位球体积的 $99\%$ 以上。
设随机向量 $X$ 在 $\mathbb{R}^n$ 的欧几里得单位球中均匀分布。证明：
$$ \mathbb{E}\|X\|_2 = \frac{n}{n+1}. $$把定理 0.0.4 中的 $N$ 改进为 $N/n$。设 $P$ 是一个有 $N\ge n$ 个顶点的多胞体，且包含在 $\mathbb{R}^n$ 的欧几里得单位球 $B$ 中。证明：
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left( C\sqrt{\frac{\log(eN/n)}{n}} \right)^n, $$其中 $C>0$ 是一个绝对常数。