一句话定位
Appetizer 的作用是用 approximate Caratheodory theorem 展示一个高维概率的核心套路：把确定性几何问题随机化，再用平均意义上的好性质推出确定性对象存在。
本篇导读
Appetizer 的核心问题是：如何用随机抽样证明一个确定性的几何近似结论？它不是预备知识列表，而是整本书的一个微型样板。
| 部分 | 内容 | 在主线中的作用 |
|---|---|---|
| 凸组合随机化 | 把 $x\in\operatorname{conv}(T)$ 写成某个随机向量 $Z$ 的期望 | 把确定性几何点转成概率对象 |
| Approximate Caratheodory | 用 $k$ 个独立样本的平均近似 $\mathbb EZ$ | 从期望误差推出存在一个具体近似 |
| Polytope covering | 把所有 $k$ 次抽样平均当作覆盖中心 | 从点的近似表示转到集合覆盖 |
| Volume bound | 用覆盖球总体积控制 polytope 体积 | 得到高维几何结论 |
| Exercises | 检查紧性、计数改进和 Hoeffding 型强化 | 把概率方法从均方误差升级到尾界 |
本篇读法是：先看清“凸组合 = 随机变量期望”，再看样本均值如何给出近似，最后看近似点集如何变成 covering 和 volume estimate。
本页使用方式
Appetizer 不适合按“定义逐条背”的方式读。初学者应先抓住一件事：概率方法怎样证明一个确定性的几何覆盖结论。
| 你现在卡在哪里 | 先看哪里 | 读完要能说出的句子 |
|---|---|---|
| 不理解“随机化证明确定性存在性” | 本篇学习路线、Theorem 0.0.2 卡片 | “把凸组合写成随机向量的期望，再抽样；平均表现好就存在一个具体好样本。” |
| 看不懂 Maurey empirical method | Theorem 0.0.2 完整证明 | “证明目标是找 $k$ 个点近似 $x$，不是估计随机样本本身。” |
| 覆盖数和体积界没有画面 | Corollary 0.0.3、Theorem 0.0.4 完整证明 | “$N$ 个顶点经过 $k$ 次抽样产生 $N^k$ 个中心；球覆盖再转成体积上界。” |
| 想知道哪些跳步已经补齐 | 正文读者自证补全、Exercises 0.1-0.9 | “原文留给读者的紧性、二项式估计、Hoeffding 入口都在练习里。” |
| 只想检查是否读懂 | 易混点、学习检查表 | “我能从 $x\in\operatorname{conv}(T)$ 自己构造随机变量 $Z$。” |
本篇主线
Appetizer 的主线很短，但代表了全书的基本思维方式：先把确定性对象随机化，再用概率估计证明存在性，最后把点的近似表示转成集合的覆盖结论。
| 推进层 | 要解决的问题 | 关键转折 | 读完后的抓手 |
|---|---|---|---|
| 随机化 | 凸组合为什么能引入概率？ | 把 $x=\sum_i\lambda_i z_i$ 读成 $x=\mathbb EZ$ | 凸组合就是一个离散随机向量的期望 |
| 近似 | 怎样用少量点近似原来的 $x$？ | 用 $k$ 个独立样本的平均近似 $\mathbb EZ$ | 方差计算给出 $1/\sqrt k$ 误差尺度 |
| 固定化 | 随机样本好，为什么推出确定性存在？ | 期望误差小意味着至少有一个样本不差 | 概率方法提供存在性证明 |
| 覆盖 | 点的近似如何变成集合结论？ | 所有 $k$ 次抽样平均组成覆盖中心 | 中心数 $N^k$ 与覆盖半径共同控制体积 |
| 强化 | 练习在训练什么？ | 从均方误差、计数和尾界三个方向加固主定理 | 看见 Hoeffding 型强化如何进入高维几何 |
本篇学习路线
Appetizer 只讲一个核心套路：把凸组合看成随机变量的期望，随机抽样得到平均意义上的好近似，再固定一个好的样本，实现确定性存在性。
- 凸组合可以改写为 $\mathbb E Z$。
- 样本均值可以近似 $\mathbb E Z$。
- 近似点集可以覆盖 polytope，并推出体积界。
把几何点变成随机变量
若 $x=\sum_i\lambda_i z_i$，就令随机向量 $Z$ 以概率 $\lambda_i$ 取值 $z_i$。于是 $x=\mathbb E Z$。这是 Maurey empirical method 的入口。
用样本均值近似期望
独立抽样 $Z_1,\ldots,Z_k$ 后，$\frac1k\sum_j Z_j$ 是 $k$ 个点的等权平均。方差计算给出平均误差平方 $\le 1/k$，所以存在一个具体样本误差 $\le 1/\sqrt k$。
从近似表示走向覆盖和体积
对有 $N$ 个顶点的 polytope，所有 $k$ 个顶点等权平均至多有 $N^k$ 个。这些点形成覆盖中心；半径来自 approximate Caratheodory。再用“覆盖总体积”控制 polytope 体积。
分层阅读路线
| 层次 | 先抓什么 | 推荐入口 | 暂时怎么处理 |
|---|---|---|---|
| 第一遍：主线阅读 | 凸组合随机化、样本均值近似、covering 到 volume | 本篇主线、Theorem 0.0.2 卡片 | 先看懂“随机样本好 -> 存在确定性样本好”，不急着优化常数。 |
| 第二遍：证明精读 | Maurey empirical method、polytope covering、volume bound | Theorem 0.0.2、Corollary 0.0.3、Theorem 0.0.4 完整证明 | 把方差计算、$N^k$ 计数和体积缩放逐步写出来。 |
| 第三遍：习题与应用 | 紧性、计数改进、Hoeffding 型强化 | Exercises 0.1-0.9 | 先按“基础验证 -> 核心证明 -> 高价值挑战”做。 |
| 专题回看 | 凸几何中的 covering、Carl-Pajor、approximate Caratheodory | 第 10 部分深入阅读路线 | 为后续读 asymptotic convex geometry 做入口。 |
核心对象与符号表
| 符号 / 对象 | 在原书中的角色 | 学习时要抓住的意思 |
|---|---|---|
| $T\subset\mathbb R^n$ | 被取凸包的点集，包含在 Euclidean 单位球中。 | 原始候选点集合；之后抽样只能从 $T$ 里取点。 |
| $\operatorname{conv}(T)$ | $T$ 的 convex hull。 | 所有凸组合形成的集合；Appetizer 的目标是在这里近似任意点。 |
| $x\in\operatorname{conv}(T)$ | 要被近似的点。 | 先把它写成精确凸组合，再把凸组合解释成随机变量期望。 |
| $Z$ | 由凸组合系数定义的离散随机向量。 | 人为引入的随机化工具，满足 $\mathbb E Z=x$。 |
| $Z_1,\ldots,Z_k$ | $Z$ 的独立拷贝。 | 它们的样本均值是 $k$ 个点的等权平均。 |
| $k$ | 抽样次数 / 等权平均中点的个数。 | 控制误差半径 $1/\sqrt k$，也控制覆盖中心数量。 |
| $P$ | 有 $N$ 个顶点的 polytope。 | 把 approximate Caratheodory 用到有限顶点凸包上。 |
| $N^k$ | 有序选择 $k$ 个顶点的粗略计数。 | 给 Corollary 0.0.3 的覆盖中心数量；Exercise 0.9 会改进它。 |
| $B$ | $\mathbb R^n$ 的 Euclidean 单位球。 | 体积比较的参照物，也是高维直觉的来源。 |
关键定理卡片
条件：$T\subset\mathbb R^n$ 位于 Euclidean 单位球中，$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}. $$条件：$P\subset\mathbb R^n$ 是包含在单位球中的 polytope，有 $N$ 个顶点。
结论：对每个 $k\in\mathbb N$，$P$ 可由至多 $N^k$ 个半径 $1/\sqrt{k}$ 的 Euclidean 球覆盖。
条件：$P$ 是有 $N$ 个顶点的 polytope，且 $P$ 包含在 $\mathbb R^n$ 的 Euclidean 单位球 $B$ 中。
结论：
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(3\sqrt{\frac{\log N}{n}}\right)^n. $$Theorem 0.0.4 的读法不是“多面体体积有一个公式”，而是：在高维中，如果顶点数 $N$ 没有达到足够大的指数级，$\operatorname{conv}\{z_1,\ldots,z_N\}$ 即使看起来很复杂，也只能占单位球很小一部分体积。
关键定理完整证明
原书只陈述了 Caratheodory 定理。标准证明如下。设
$$ x=\sum_{i=1}^m\lambda_i z_i,\qquad \lambda_i\ge0,\qquad \sum_{i=1}^m\lambda_i=1. $$若 $m\le n+1$，已经完成。若 $m>n+1$，则 $z_1,\ldots,z_m$ 仿射相关，所以存在不全为零的 $a_1,\ldots,a_m$，使得
$$ \sum_{i=1}^m a_i z_i=0, \qquad \sum_{i=1}^m a_i=0. $$这些 $a_i$ 中必有正有负。取
$$ t=\min_{a_i>0}\frac{\lambda_i}{a_i}. $$定义新系数 $\lambda_i'=\lambda_i-ta_i$。则 $\lambda_i'\ge0$，至少有一个 $\lambda_i'=0$，并且
$$ \sum_i\lambda_i'=1,\qquad \sum_i\lambda_i' z_i = \sum_i\lambda_i z_i - t\sum_i a_i z_i = x. $$因此可以删去一个点。重复这个过程，直到剩下至多 $n+1$ 个点。
证明思路
把确定性的凸组合改写成随机向量的期望，再用 $k$ 个独立样本的样本均值来构造等权平均。均方误差估计说明随机构造平均表现很好，因此存在一个具体样本实现满足同样的误差界。
完整证明
固定 $x\in\operatorname{conv}(T)$。由凸包定义，可取 $z_1,\ldots,z_m\in T$ 与 $\lambda_i\ge0$，$\sum_i\lambda_i=1$，使得
$$ x=\sum_{i=1}^m\lambda_i z_i. $$定义随机向量 $Z$，令
$$ \mathbb P\{Z=z_i\}=\lambda_i,\qquad i=1,\ldots,m. $$于是
$$ \mathbb EZ=\sum_{i=1}^m\lambda_i z_i=x. $$令 $Z_1,\ldots,Z_k$ 为 $Z$ 的独立同分布副本。样本均值 $\frac1k\sum_{j=1}^kZ_j$ 是 $k$ 个 $T$ 中点的等权平均。下面估计它到 $x$ 的均方误差：
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^kZ_j\right\|_2^2 = \frac1{k^2} \mathbb E\left\|\sum_{j=1}^k(Z_j-x)\right\|_2^2. $$记 $Y_j=Z_j-x$。则 $Y_j$ 独立且 $\mathbb EY_j=0$。展开平方：
$$ \mathbb E\left\|\sum_{j=1}^kY_j\right\|_2^2 = \sum_{i,j=1}^k\mathbb E\langle Y_i,Y_j\rangle. $$当 $i\ne j$ 时，由独立性与零均值得
$$ \mathbb E\langle Y_i,Y_j\rangle = \langle\mathbb EY_i,\mathbb EY_j\rangle = 0. $$所以只剩对角项：
$$ \mathbb E\left\|\sum_{j=1}^kY_j\right\|_2^2 = \sum_{j=1}^k\mathbb E\|Y_j\|_2^2 = k\,\mathbb E\|Z-\mathbb EZ\|_2^2. $$再由向量方差恒等式，
$$ \mathbb E\|Z-\mathbb EZ\|_2^2 = \mathbb E\|Z\|_2^2-\|\mathbb EZ\|_2^2 \le \mathbb E\|Z\|_2^2 \le 1, $$其中最后一步使用 $Z\in T$ 且 $T$ 包含在单位球中。因此
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^kZ_j\right\|_2^2 \le \frac1k. $$由于误差平方是非负随机变量，若所有样本实现都大于 $1/k$，则其期望也会大于 $1/k$，矛盾。因此存在某个样本实现 $x_1,\ldots,x_k\in T$，使得
$$ \left\|x-\frac1k\sum_{j=1}^kx_j\right\|_2^2 \le \frac1k. $$开方即得
$$ \left\|x-\frac1k\sum_{j=1}^kx_j\right\|_2 \le \frac1{\sqrt k}. $$设 $T$ 为 $P$ 的顶点集合。定义覆盖中心集合
$$ \mathcal N = \left\{ \frac1k\sum_{j=1}^k x_j: x_j\in T \right\}. $$因为 $T$ 有 $N$ 个点，选择有序的 $k$ 个顶点、允许重复，最多有 $N^k$ 种，所以 $|\mathcal N|\le N^k$。
任取 $x\in P=\operatorname{conv}(T)$。由 Theorem 0.0.2，存在 $x_1,\ldots,x_k\in T$，使
$$ \left\| x-\frac1k\sum_{j=1}^kx_j \right\|_2 \le \frac1{\sqrt k}. $$右侧的等权平均属于 $\mathcal N$。因此每个 $x\in P$ 都落在某个以 $\mathcal N$ 中点为中心、半径 $1/\sqrt k$ 的球内，这些球覆盖 $P$。
证明思路
先用 Corollary 0.0.3 把 $P$ 覆盖成许多小球。球的数量至多 $N^k$，半径为 $1/\sqrt k$。用覆盖球总体积控制 $P$ 的体积，然后选择合适的 $k$ 平衡“球的数量”和“球的半径”。
完整证明
若 $N=1$，则 $P$ 只是一个点，$n$ 维体积为 $0$，结论成立。以下设 $N\ge2$。
由 Corollary 0.0.3，$P$ 可由至多 $N^k$ 个半径为 $1/\sqrt k$ 的 Euclidean 球覆盖。每个这样的球体积为 $k^{-n/2}\operatorname{Vol}(B)$，因为 $n$ 维体积在半径缩放 $r$ 时乘以 $r^n$。于是
$$ \operatorname{Vol}(P) \le N^k k^{-n/2}\operatorname{Vol}(B), $$即
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \frac{N^k}{k^{n/2}}. \tag{*} $$这个界对每个 $k\in\mathbb N$ 成立。先把 $k$ 暂时看成正实数，优化右侧。取对数：
$$ \phi(k)=k\log N-\frac n2\log k. $$求导并令导数为零：
$$ \phi'(k)=\log N-\frac n{2k}=0, \qquad k_0=\frac n{2\log N}. $$若直接代入 $k_0$，则
$$ \frac{N^{k_0}}{k_0^{n/2}} = \exp\left(\frac n2\right) \left(\frac{2\log N}{n}\right)^{n/2} = \left(\sqrt{\frac{2e\log N}{n}}\right)^n. $$但 $k$ 必须是整数。取 $k=\lceil k_0\rceil$。若 $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}} = N\left(\sqrt{\frac{2e\log N}{n}}\right)^n. $$若 $N\le e^{n/9}$，则
$$ N\left(\sqrt{\frac{2e\log N}{n}}\right)^n \le \left(e^{1/9}\sqrt{2e}\right)^n \left(\sqrt{\frac{\log N}{n}}\right)^n. $$由于 $e^{1/9}\sqrt{2e}<3$，所以
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(3\sqrt{\frac{\log N}{n}}\right)^n. $$若 $N>e^{n/9}$，则 $3\sqrt{\log N/n}>1$，从而目标右侧大于 $1$。另一方面 $P\subset B$，所以
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le 1, $$结论同样成立。两种情况合并即证 Theorem 0.0.4。
易混点
原问题是确定性的：给定 $x\in\operatorname{conv}(T)$，要找确定的 $x_1,\ldots,x_k\in T$。证明中引入 $Z$ 只是把凸组合系数 $\lambda_i$ 变成抽样概率。随机性是工具，不是结论的一部分。
若 $\mathbb E Y\le a$ 且 $Y\ge0$，就不可能所有样本都满足 $Y>a$；因此至少存在一个样本使 $Y\le a$。Approximate Caratheodory 最后一步用的正是这个存在性逻辑。
Corollary 0.0.3 用所有有序 $k$ 元组生成覆盖中心，所以得到 $N^k$。这足够推出 Theorem 0.0.4，但并不精细。Exercise 0.9 的 Carl-Pajor 改进会把“有序选择”换成“带重复的多重集合”计数，即 $\binom{N+k-1}{k}$。
证明 Theorem 0.0.4 时，只需要 $P$ 被这些球覆盖，因此 $\operatorname{Vol}(P)$ 不超过所有覆盖球体积之和。球之间可以大量重叠；这里用的是 union bound 的体积版本。
Exercises 0.1-0.9 完整证明
先按训练目标分配精力：
| 题目 | 难度 | 训练目标 | 证明 |
|---|---|---|---|
| 0.1 | 基础 | 验证方差恒等式，服务 Theorem 0.0.2 的误差计算。 | 跳转 |
| 0.2 | 进阶 | 理解“期望最小化均方误差”。 | 跳转 |
| 0.3 | 基础 | 证明独立和的方差可加性。 | 跳转 |
| 0.4 | 基础 | 用 Rademacher 随机化证明确定性向量平衡。 | 跳转 |
| 0.5 | 进阶 | 说明 approximate Caratheodory 的 $1/\sqrt k$ 量级基本不能改。 | 跳转 |
| 0.6 | 基础 | 掌握二项式和估计，为 Carl-Pajor 改进做计数准备。 | 跳转 |
| 0.7 | 基础 | 用体积缩放理解高维球的薄壳现象。 | 跳转 |
| 0.8 | 基础 | 把薄壳现象转成随机半径的分布函数和期望。 | 跳转 |
| 0.9 | 进阶 | 把有序计数替换为多重集合计数，得到更强体积界。 | 跳转 |
0.1-0.3：方差恒等式
这三题是 Maurey empirical method 的计算底座。目标是熟悉“展开范数平方、利用独立性消掉交叉项”。
完整证明 (a)：把范数平方写成内积，展开得到
$$ \|Z-\mathbb{E}Z\|_2^2 = \|Z\|_2^2 -2\langle Z,\mathbb{E}Z\rangle +\|\mathbb{E}Z\|_2^2. $$两边取期望，并用 $\mathbb E\langle Z,\mathbb EZ\rangle=\langle\mathbb EZ,\mathbb EZ\rangle=\|\mathbb EZ\|_2^2$，得到
$$ \mathbb E\|Z-\mathbb EZ\|_2^2 = \mathbb E\|Z\|_2^2-\|\mathbb EZ\|_2^2. $$完整证明 (b)：展开独立副本的距离：
$$ \mathbb E\|Z-Z'\|_2^2 = \mathbb E\|Z\|_2^2+\mathbb E\|Z'\|_2^2 -2\mathbb E\langle Z,Z'\rangle. $$由于 $Z'$ 与 $Z$ 同分布，前两项相同；由于二者独立，
$$ \mathbb E\langle Z,Z'\rangle = \langle \mathbb EZ,\mathbb EZ'\rangle = \|\mathbb EZ\|_2^2. $$因此
$$ \mathbb E\|Z-Z'\|_2^2 = 2\mathbb E\|Z\|_2^2-2\|\mathbb EZ\|_2^2 = 2\mathbb E\|Z-\mathbb EZ\|_2^2, $$即得结论。
证明：对任意 $a\in\mathbb R^n$，写成
$$ Z-a=(Z-\mathbb{E}Z)+(\mathbb{E}Z-a). $$平方取期望后，交叉项为 $0$，所以
$$ \mathbb{E}\|Z-a\|_2^2 = \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 + \|\mathbb{E}Z-a\|_2^2. $$右侧第一项与 $a$ 无关，第二项非负，并且当 $a=\mathbb EZ$ 时取到 $0$。所以最小值正是
$$ \mathbb E\|Z-\mathbb EZ\|_2^2. $$证明：展开平方：
$$ \mathbb{E}\biggl\|\sum_{j=1}^k Z_j\biggr\|_2^2 = \sum_{i,j}\mathbb{E}\langle Z_i,Z_j\rangle. $$当 $i\ne j$ 时，由独立性和零均值得到
$$ \mathbb E\langle Z_i,Z_j\rangle = \langle\mathbb EZ_i,\mathbb EZ_j\rangle = 0. $$于是交叉项全部消失，只剩对角项：
$$ \mathbb{E}\biggl\|\sum_{j=1}^k Z_j\biggr\|_2^2 = \sum_{j=1}^k\mathbb E\|Z_j\|_2^2. $$0.4-0.5：概率方法与近似 Caratheodory 的紧性
这两题分别训练两个判断：概率方法如何给出确定性符号选择，以及 $1/\sqrt k$ 误差为什么不能随便改进。
完整证明 (a)：令 $\varepsilon_1,\ldots,\varepsilon_n$ 为独立 Rademacher 随机变量，即 $\mathbb P\{\varepsilon_i=1\}=\mathbb P\{\varepsilon_i=-1\}=1/2$。考虑随机和
$$ S=\sum_{i=1}^n\varepsilon_i x_i. $$各项 $\varepsilon_i x_i$ 独立且均值为零。由 Exercise 0.3，
$$ \mathbb{E}\|S\|_2^2 = \sum_{i=1}^n\mathbb E\|\varepsilon_i x_i\|_2^2 = \sum_{i=1}^n\|x_i\|_2^2 \le n. $$若所有符号选择都满足 $\|S\|_2^2>n$，则平均也会大于 $n$，矛盾。因此存在一个具体符号选择使 $\|S\|_2^2\le n$，即 $\|S\|_2\le\sqrt n$。
完整证明 (b)：取 $x_i=e_i$，即标准正交基。任意符号选择都给出
$$ \left\|\sum_{i=1}^n\varepsilon_i e_i\right\|_2^2 = \sum_{i=1}^n\varepsilon_i^2 = n. $$所以范数恒等于 $\sqrt n$，一般不能把半径降低。
证明：取 $T=\{e_1,\ldots,e_n\}$，并令
$$ x=\frac1n\sum_{i=1}^n e_i. $$因为 $x$ 是 $T$ 中 $n$ 个点的等权凸组合，所以 $x\in\operatorname{conv}(T)$。现在任取 $T$ 中 $k$ 个点，并考虑它们的任意凸组合 $y=\sum_{j=1}^k\lambda_jx_j$。设 $S$ 是 $y$ 的支撑，则 $|S|\le k$，且 $\sum_{i\in S}y_i=1$。于是
$$ \|x-y\|_2^2 = \sum_{i\in S}\left(y_i-\frac1n\right)^2 + \sum_{i\notin S}\frac1{n^2} = \sum_{i\in S}y_i^2-\frac1n. $$由 Cauchy-Schwarz 不等式，
$$ \sum_{i\in S}y_i^2 \ge \frac1{|S|} \ge \frac1k. $$因此
$$ \|x-y\|_2^2 \ge \frac1k-\frac1n. $$开方得到题设结论。这里主要关心 $k\le n$；若 $k>n$，右侧不再给出正的下界，题目的渐近紧性讨论也不需要这一情形。
0.6-0.9：组合计数与高维体积
这一组连接 Appetizer 后半段：二项式估计用于控制支撑数量，体积缩放解释高维薄壳，Carl-Pajor 定理改进 covering centers 的计数。
证明：中间的不等式来自求和项中包含 $j=k$ 这一项。先看下界：
$$ \binom nk = \prod_{i=0}^{k-1}\frac{n-i}{k-i}. $$由于 $k\le n$，每个因子都满足
$$ \frac{n-i}{k-i}\ge\frac nk, $$所以 $\binom nk\ge(n/k)^k$。
再证上界。令 $x=k/n\le1$。当 $0\le j\le k$ 时，$x^j\ge x^k$，所以
$$ \sum_{j=0}^k\binom nj \le x^{-k}\sum_{j=0}^k\binom njx^j \le x^{-k}(1+x)^n. $$代入 $x=k/n$，并用 $1+u\le e^u$，得到
$$ x^{-k}(1+x)^n = \left(\frac nk\right)^k \left(1+\frac kn\right)^n \le \left(\frac{en}{k}\right)^k. $$
证明：若 $n\le5$，则 $5/n\ge1$，单位球内任意点到球面的距离都不超过 $1$，因此整个单位球都落在该薄壳中。
下面设 $n>5$。距离球面超过 $5/n$ 的点，正好落在半径 $1-5/n$ 的同心球中。因此这部分体积占比为
$$ \left(1-\frac5n\right)^n \le e^{-5} <0.01. $$补集就是距离球面不超过 $5/n$ 的薄壳，所以它的体积占比大于 $1-0.01=99\%$。
证明：令 $R=\|X\|_2$。由于 $X$ 在单位球中均匀分布，且半径为 $r$ 的球体积是单位球体积的 $r^n$ 倍，所以
$$ \mathbb{P}\{R\le r\}=r^n,\qquad 0\le r\le1. $$因此 $R$ 的密度为 $f_R(r)=nr^{n-1}$，$0\le r\le1$。于是
$$ \mathbb{E}R = \int_0^1 r\cdot nr^{n-1}\,dr = \frac{n}{n+1}. $$证明：Theorem 0.0.4 中用了粗计数 $N^k$。这里改用更精确的计数：Theorem 0.0.2 输出的是 $k$ 个顶点的等权平均，允许重复；不同的有序 $k$ 元组可能给出同一个多重集合。因此覆盖中心数至多为大小为 $k$ 的多重集合数
$$ M_k = \binom{N+k-1}{k}. $$若 $1\le k\le N$，由 Exercise 0.6 得到
$$ M_k \le \binom{2N}{k} \le \left(\frac{2eN}{k}\right)^k. $$于是，与 Theorem 0.0.4 相同的覆盖-体积论证给出
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \binom{N+k-1}{k}k^{-n/2} \le \left(\frac{2eN}{k}\right)^k k^{-n/2}. $$记
$$ L=\log\left(\frac{eN}{n}\right). $$由于 $N\ge n$，有 $L\ge1$。若 $L\ge n$，则选取足够大的绝对常数 $C$ 后，右侧目标界
$$ \left(C\sqrt{\frac Ln}\right)^n $$已经不小于 $1$，而 $\operatorname{Vol}(P)\le\operatorname{Vol}(B)$，结论平凡。
下面设 $L<n$，取
$$ k=\left\lceil\frac n{2L}\right\rceil. $$则 $1\le k\le n\le N$，所以前面的多重集合计数估计可以使用；并且 $k\asymp n/L$。代入上式：
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(\frac{2eN}{k}\right)^k k^{-n/2}. $$第一因子只贡献一个指数常数。具体地，因 $k\asymp n/L$，
$$ \log\left(\frac{2eN}{k}\right) \le C_1 L $$对某个绝对常数 $C_1$ 成立，所以
$$ \left(\frac{2eN}{k}\right)^k \le \exp(C_2 n). $$另一方面，由 $k\ge n/(2L)$，
$$ k^{-n/2}\le \left(\frac{2L}{n}\right)^{n/2}. $$合并得到
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \exp(C_2n) \left(\frac{2L}{n}\right)^{n/2} = \left(C\sqrt{\frac{\log(eN/n)}{n}}\right)^n, $$其中 $C>0$ 是绝对常数。这就是 Carl-Pajor 型改进。
学习检查表
- [ ] 能把凸组合解释成随机变量的期望。
- [ ] 能复现 approximate Caratheodory 的 empirical method 证明。
- [ ] 能补出 Theorem 0.0.2 中独立和方差可加的展开计算。
- [ ] 能补出 Theorem 0.0.4 中优化 $k$ 和常数 $3$ 的检查。
- [ ] 能说明为什么 $N^k$ 个中心足以覆盖 $N$ 顶点 polytope。
- [ ] 能说明 Exercise 0.9 为什么使用 $\binom{N+k-1}{k}$ 而不是 $N^k$。
- [ ] 能从 covering number 推出 polytope 的体积上界。
- [ ] 能解释这个例子为什么体现“概率方法证明确定性存在性”。
后续衔接
Appetizer 之后进入 第 1 章学习笔记，主要补齐后续章节会反复使用的分析与概率语言。本篇的 covering 思想会在第 4.2 节的 covering / packing numbers 中正式系统化；“随机抽样构造确定性对象”的套路也会在随机矩阵、随机过程和 chaining 中反复出现。