Tao–Vu · 加性组合学 · 第 7 章 Littlewood–Offord 问题
7.3 埃森集中不等式The Esséen concentration inequality
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 引理 / 命题 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标前面几节关心的是随机游走 \(X_v^{(\mu)}\) 恰好落到某一个点 \(x\) 的概率。但很多时候我们真正想知道的是：它落进一整片区域（比如一个立方体、一个球）的概率有多大。本节给出一件处理这类“区域集中”问题的趁手工具——埃森（Esséen）集中不等式。它的核心思想是：用特征函数（傅里叶变换）\(\mathbb{E}\,e(\xi\cdot X)\) 的大小，去控制概率分布的集中程度。我们会先把不等式讲清楚、证出来，再把它套到随机游走上，得到一个高维的集中估计（命题 7.18）。
从“落到一点”到“落进一片区域”
在若干应用中，我们关心的不是随机游走 \(X_v^{(\mu)}\) 最终停在某个指定点的概率，而是它落进空间中某块区域（例如一个立方体）的概率。在某些“离散”情形下（例如当 \(v_1,\dots,v_n\) 取值于一个格点时），我们可以简单地用并集界（union bound）从前者过渡到后者，但这并不总是最好的办法。处理一般的集中问题时，一件有用的工具是埃森的一个简单集中不等式。
为什么并集界不总是够好
设区域是一个边长 \(R\) 的立方体，里面含有大约 \(R^d\) 个格点。并集界的做法是：把落到区域里的概率，拆成分别落到每一个格点的概率之和：
\[\mathbb{P}(X\in \text{区域})\le \sum_{x\in\text{区域}}\mathbb{P}(X=x).\]
如果每个点的概率都 \(\le p\)，这给出 \(\le R^d\,p\)。当 \(R\) 较大、或维数 \(d\) 较高时，因子 \(R^d\) 会把估计放得很松。更糟的是，若 \(v_j\) 不落在格点上（取连续值），区域里根本没有“可数的点”可拆，并集界完全失效。埃森不等式则不依赖这种逐点拆分，对连续与离散一视同仁。
记号准备
记号记 \(e(x):=\exp(2\pi i x)\)。对于向量，\(\xi\cdot X\) 表示 \(\mathbb{R}^d\) 上通常的内积，\(|\xi|\) 表示通常的（欧氏）长度。于是
\[\mathbb{E}\,e(\xi\cdot X)=\mathbb{E}\,\exp\!\big(2\pi i\,\xi\cdot X\big)\]
就是随机变量 \(X\) 的特征函数（在 \(\xi\) 处取值），即概率分布的傅里叶变换。
直觉：特征函数为什么能“看出”集中
取 \(d=1\)。如果 \(X\) 高度集中（几乎总等于同一个值 \(a\)），那么 \(e(\xi X)\approx e(\xi a)\) 是一个长度为 \(1\) 的复数，对所有 \(\xi\) 几乎都不抵消，于是 \(|\mathbb{E}\,e(\xi X)|\approx 1\)，在很宽的 \(\xi\) 区间上都接近 \(1\)。
反之，如果 \(X\) 摊得很开（分布很“平”），不同取值贡献的复数 \(e(\xi X)\) 朝各个方向，互相抵消，\(|\mathbb{E}\,e(\xi X)|\) 很快就掉到接近 \(0\)。
所以：特征函数在原点附近保持“大”的范围越宽，分布就越集中。埃森不等式正是把这句话变成一条精确的不等式——用 \(\int_{|\xi|<\varepsilon}|\mathbb{E}\,e(\xi\cdot X)|\,d\xi\) 这个积分来量化“保持大的范围有多宽”。
埃森集中不等式
引理 7.17（埃森集中不等式）[101]
设 \(X\) 是在 \(\mathbb{R}^d\) 中取有限多个值的随机变量。设 \(x_0\in\mathbb{R}^d\)，并设 \(R,\varepsilon>0\)。则
\[\sup_{x_0\in\mathbb{R}^d}\mathbb{P}\big(|X-x_0|\le R\big)=O\!\left(\frac{R}{\sqrt d}+\frac{\sqrt d}{\varepsilon}\right)^{\!d}\int_{\xi\in\mathbb{R}^d:\,|\xi|<\varepsilon}\big|\mathbb{E}\,e(\xi\cdot X)\big|\,d\xi.\]
这里 \(e(x):=\exp(2\pi i x)\)，\(\xi\cdot X\) 是 \(\mathbb{R}^d\) 上通常的内积，\(|\xi|\) 是通常的长度。
怎么读这条不等式
左边 \(\sup_{x_0}\mathbb{P}(|X-x_0|\le R)\) 是 \(X\) 落进任何一个半径 \(R\) 的球的最大概率——它度量了分布最“拥挤”的地方有多拥挤（即集中函数）。右边由两部分相乘：
- 几何因子 \(\big(R/\sqrt d+\sqrt d/\varepsilon\big)^{d}\)：只跟球的半径 \(R\)、自由参数 \(\varepsilon\) 和维数 \(d\) 有关，是覆盖论证带来的“体积代价”。
- 分析因子 \(\displaystyle\int_{|\xi|<\varepsilon}|\mathbb{E}\,e(\xi\cdot X)|\,d\xi\)：特征函数在小邻域 \(|\xi|<\varepsilon\) 上的积分，正是前面说的“特征函数保持大的程度”。
证明.
通过把 \(X\) 与 \(R\) 同时按 \(\varepsilon\) 作缩放，我们可以不妨设 \(\varepsilon=\sqrt d\)。于是一个简单的覆盖论证（例如借助推论 3.15）表明，只需证明：存在某个小的绝对常数 \(c>0\)，使得对所有 \(x_0\in\mathbb{R}^d\) 有
\[\mathbb{P}\big(|X-x_0|\le c\sqrt d\big)\le O(1)^d\int_{\xi\in\mathbb{R}^d:\,|\xi|<\sqrt d}\big|\mathbb{E}\,e(\xi\cdot X)\big|\,d\xi.\]
再通过把 \(X\) 平移 \(x_0\)（这不影响右边），我们可以不妨设 \(x_0=0\)。
现在，由标准的高斯积分恒等式
\[\int_{\xi\in\mathbb{R}^d} e^{-\pi C|\xi|^2}\,e(\xi\cdot X)\,d\xi=C^{-d/2}\,e^{-\pi|X|^2/C}\qquad(\forall\,C>0),\]
我们看出
\[\left|\int_{\xi\in\mathbb{R}^d:\,|\xi|<\sqrt d/2} e^{-\pi C|\xi|^2}\,e(\xi\cdot X)\,d\xi\right|=\Omega(1)^d\tag{7.4}\]
对一切满足 \(|X|\le c\sqrt d\) 的 \(X\) 成立——只要 \(c\) 取得足够小、\(C\) 取得足够大。把它平方，得到
\[\int_{\xi\in\mathbb{R}^d:\,|\xi|<\sqrt d} e(\xi\cdot X)\,w(\xi)\,d\xi=\Omega(1)^d\,\mathbf{1}\big(|X|\le c\sqrt d\big),\]
其中
\[w(\xi):=\int_{|\xi_1|,\,|\xi-\xi_1|<\sqrt d/2} e^{-\pi C|\xi_1|^2}\,e^{-\pi C|\xi-\xi_1|^2}\,d\xi_1.\]
对两边取期望，得到
\[\int_{\xi\in\mathbb{R}^d:\,|\xi|<\sqrt d}\big|\mathbb{E}\,e(\xi\cdot X)\big|\,w(\xi)\,d\xi\ge\Omega(1)^d\,\mathbb{P}\big(|X|\le c\sqrt d\big).\]
由 (3.8) 我们看出 \(w(\xi)=O(1)^d\)，于是结论得证。♦
把证明拆成最小的步子
- 归一化（缩放）。 不等式两边对 \(X,R,\varepsilon\) 的同步缩放是“齐次”的，所以可以先把尺度调成最方便的 \(\varepsilon=\sqrt d\)。这一步只是为了让后面的数字干净。
- 覆盖论证：从大球退到固定小球。 任何半径 \(R\) 的大球，都能用 \(O\!\big(R/\sqrt d\big)^d\) 个半径 \(c\sqrt d\) 的小球盖住。落进大球 \(\Rightarrow\) 落进某个小球，于是 \[\mathbb{P}(|X-x_0|\le R)\le \big(\text{小球个数}\big)\times\max_{x_1}\mathbb{P}(|X-x_1|\le c\sqrt d).\] 这正是几何因子 \(\big(R/\sqrt d+\sqrt d/\varepsilon\big)^d\) 的来源。所以只剩下半径为 \(c\sqrt d\) 的固定小球要处理。
- 平移到原点。 把球心移到 \(0\)，不妨证 \(\mathbb{P}(|X|\le c\sqrt d)\) 的界。
- 用高斯做“探针”。 高斯函数 \(e^{-\pi C|\xi|^2}\) 的傅里叶变换还是高斯 \(C^{-d/2}e^{-\pi|X|^2/C}\)。把积分限制在 \(|\xi|<\sqrt d/2\) 上，当 \(|X|\) 小时（\(\le c\sqrt d\)），相位 \(e(\xi\cdot X)\) 转得不快、不互相抵消，于是积分的绝对值仍然 \(\ge\Omega(1)^d\)，这就是 (7.4)。也就是说：只要 \(X\) 离原点近，这个高斯加权的傅里叶积分就一定不小。
- 平方 = 自相关。 把 (7.4) 平方，两个积分相乘合并成关于 \(\xi=\xi_1+(\xi-\xi_1)\) 的单重积分，权重 \(w(\xi)\) 就是高斯的自卷积（自相关）。平方后右边自然出现指示函数 \(\mathbf 1(|X|\le c\sqrt d)\)：\(X\) 近则 \(\ge\Omega(1)^d\)，否则 \(\ge 0\)。
- 取期望，换出概率与特征函数。 对随机的 \(X\) 取期望：右边 \(\mathbb{E}\,\mathbf 1(|X|\le c\sqrt d)=\mathbb{P}(|X|\le c\sqrt d)\)；左边把期望搬进积分，并用 \(|\mathbb{E}(\cdots)|\le\mathbb{E}|\cdots|\) 得到 \(|\mathbb{E}\,e(\xi\cdot X)|\)。再用 \(w(\xi)=O(1)^d\)（来自 (3.8)）把权重去掉，就得到 \[\mathbb{P}(|X|\le c\sqrt d)\le O(1)^d\int_{|\xi|<\sqrt d}\big|\mathbb{E}\,e(\xi\cdot X)\big|\,d\xi.\] 这正是第 2 步剩下要证的核心。
用在随机游走上：式 (7.5)
特别地，把引理 7.17 用到随机变量 \(X_v^{(\mu)}\) 上（其中 \(v=(v_1,\dots,v_n)\)，\(0\le\mu\le 1\)），我们就得到引理 7.11 的如下类比： \[\mathbb{P}\big(\,|X_v^{(\mu)}-x_0|\le R\,\big)=O\!\left(\frac{R}{\sqrt d}+\frac{\sqrt d}{\varepsilon}\right)^{\!d}\int_{\xi\in\mathbb{R}^d:\,|\xi|<\varepsilon}\ \prod_{j=1}^{n}\big|1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\big|\,d\xi.\tag{7.5}\]
为什么特征函数变成了乘积 \(\prod_j|1-\mu+\mu\cos(2\pi\xi\cdot v_j)|\)
随机游走 \(X_v^{(\mu)}=\sum_{j=1}^n \eta_j v_j\)，其中各 \(\eta_j\) 相互独立，且
\[\mathbb{P}(\eta_j=+1)=\tfrac{\mu}{2},\quad \mathbb{P}(\eta_j=-1)=\tfrac{\mu}{2},\quad \mathbb{P}(\eta_j=0)=1-\mu.\]
由独立性，特征函数是各步的乘积：
\[\mathbb{E}\,e(\xi\cdot X_v^{(\mu)})=\prod_{j=1}^n\mathbb{E}\,e(\eta_j\,\xi\cdot v_j).\]
而单步的期望是
\[\mathbb{E}\,e(\eta_j\,\xi\cdot v_j)=(1-\mu)\cdot 1+\tfrac{\mu}{2}e(\xi\cdot v_j)+\tfrac{\mu}{2}e(-\xi\cdot v_j)=1-\mu+\mu\cos(2\pi\,\xi\cdot v_j),\]
这里用了 \(\tfrac12\big(e(t)+e(-t)\big)=\cos(2\pi t)\)。把它代进引理 7.17 的 \(|\mathbb{E}\,e(\xi\cdot X)|\)，就得到 (7.5) 里的乘积。
一个应用：高维 Littlewood–Offord 集中估计
作为应用，我们给出推论 7.10 的一个高维类比，代价是损失一个依赖于维数的常数。
命题 7.18 [207], [167]
设 \(0<\mu\le 1\)，并设 \(n\) 充分大（依赖于 \(\mu\)）。设 \(v_1,\dots,v_n\) 是 \(\mathbb{R}^d\) 中的元素，且对所有 \(i\) 有 \(|v_i|\ge 1\)。则对任意 \(x_0\in\mathbb{R}^d\)，对一切 \(k\ge 1\)，
\[\mathbb{P}\big(\,|X_v^{(\mu)}-x_0|\le k\,\big)\le O(1)^d\,\frac{k}{\sqrt{\mu n}}.\]
值得注意的是，右边只随 \(k\) 线性增长，而不是人们也许会天真地预期的 \(k^d\) 增长。这反映了如下启发式：随机变量 \(X_v^{(\mu)}\) 倾向于在一维子空间上集中得最厉害（参见习题 7.2.3）。
线性 \(k\) 还是 \(k^d\)？——这是本命题的灵魂
半径为 \(k\) 的球在 \(\mathbb{R}^d\) 中体积约为 \(k^d\)。如果概率质量是“均匀摊在 \(d\) 维空间里”的，那么把球放大 \(k\) 倍，落进去的概率也应放大约 \(k^d\) 倍。
但命题说实际上只放大了 \(k\) 倍。原因：随机游走的质量并非均匀铺满 \(d\) 维，而是集中在某条一维直线方向上。沿这条线，加大半径 \(k\) 才线性多收集到质量；其余 \(d-1\) 个方向上质量本来就稀薄，加大半径几乎没多收。于是增长是一维式的 \(k\)，而不是 \(d\) 维式的 \(k^d\)。这正是 Littlewood–Offord 现象的高维体现。
证明.
由 (7.5)（取 \(R=k\) 及 \(\varepsilon=1/k\)），只需证明
\[\int_{\xi\in\mathbb{R}^d:\,|\xi|\le 1/k}\ \prod_{j=1}^{n}\big|1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\big|\,d\xi=O\!\left(\frac{1}{k\sqrt d}\right)^{\!d}\frac{k}{\sqrt{\mu n}}.\]
应用赫尔德（Hölder）不等式，我们把问题归约为证明
\[\int_{\xi\in\mathbb{R}^d:\,|\xi|\le 1/k}\big|1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\big|^{n}\,d\xi=O\!\left(\frac{1}{k\sqrt d}\cdot\frac{k}{\sqrt{\mu n}}\right)^{\!d}.\]
提供的原文 PDF 在此处（命题 7.18 的证明被赫尔德不等式归约为上面这个单变量积分后）结束。下面的“收尾推演”是为读者补足的讲解，说明这个单变量积分估计如何完成证明，并非原书正文。
收尾推演（讲解补充，非原文）：单变量积分怎么估
归约后只剩一个“单步”的积分。直觉与逐步是这样的：
- 把余弦换成下降的指数。 利用 \(1-\mu+\mu\cos(2\pi t)=1-2\mu\sin^2(\pi t)\le \exp\!\big(-2\mu\sin^2(\pi t)\big)\)（因 \(1-u\le e^{-u}\)）。所以 \[\big|1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\big|^{n}\le \exp\!\big(-2\mu n\,\sin^2(\pi\,\xi\cdot v_j)\big).\] 这把一个“振荡的、绝对值小于 \(1\)”的量，换成了一个随 \(|\xi\cdot v_j|\) 增大而迅速衰减的高斯型钟形。
- 在小区域里把 \(\sin\) 线性化。 当 \(|\xi|\le 1/k\) 时 \(\xi\cdot v_j\) 很小，\(\sin(\pi t)\approx \pi t\)，于是被积函数 \(\approx \exp\!\big(-2\pi^2\mu n\,(\xi\cdot v_j)^2\big)\)。这是一个标准的高斯，沿 \(v_j\) 方向的有效宽度约为 \(1/\sqrt{\mu n}\)。
- 算高斯积分的体积。 把这个 \(d\) 维高斯（被 \(|\xi|\le 1/k\) 截断）积出来：沿 \(v_j\) 方向贡献宽度 \(\sim 1/\sqrt{\mu n}\)，其余每个方向被球 \(|\xi|\le 1/k\) 截断、贡献宽度 \(\sim 1/k\)。于是 \[\int_{|\xi|\le 1/k}\!\exp\!\big(-2\pi^2\mu n\,(\xi\cdot v_j)^2\big)\,d\xi\ \lesssim\ \frac{1}{\sqrt{\mu n}}\cdot\Big(\frac{1}{k}\Big)^{d-1}=O\!\left(\frac{1}{k\sqrt d}\cdot\frac{k}{\sqrt{\mu n}}\right)^{\!d}\!\cdot O(1)^d,\] 正是所需的形式（\(O(1)^d\) 的依赖维数常数被允许）。这里 \(|v_j|\ge 1\) 保证了 \(v_j\) 方向上 \(\xi\cdot v_j\) 确实“走得动”，高斯才真的窄。
- 合起来。 把这个单变量界乘回几何因子 \(\big(R/\sqrt d+\sqrt d/\varepsilon\big)^d\)（此处 \(=O(k\sqrt d)^d\)），\(d\) 次幂彼此抵消，只剩一个 \(k/\sqrt{\mu n}\)： \[\mathbb{P}\big(|X_v^{(\mu)}-x_0|\le k\big)\le O(1)^d\,\frac{k}{\sqrt{\mu n}}.\] 线性的 \(k\)（而非 \(k^d\)）正是从这里来的：只有 \(v_j\) 那一个方向是“窄而长”的高斯，其余 \(d-1\) 个方向的 \(1/k\) 因子恰好与几何因子里的 \(k\) 抵消掉。♦
即时自测
- 在引理 7.17 中，若把 \(\varepsilon\) 取得很大，几何因子 \((R/\sqrt d+\sqrt d/\varepsilon)^d\) 会变小还是变大？积分因子的范围会变宽还是变窄？由此说明为什么要“平衡” \(\varepsilon\)。
- 验证单步特征函数 \(\mathbb{E}\,e(\eta_j\,\xi\cdot v_j)=1-\mu+\mu\cos(2\pi\,\xi\cdot v_j)\)，并说明当 \(\mu=1\)（即每步必走 \(\pm v_j\)）时它退化成什么。
- 命题 7.18 的右边为何是 \(k/\sqrt{\mu n}\) 而不是 \((k/\sqrt{\mu n})^d\)？用“质量集中在一维方向”这一启发式，结合上面的收尾推演第 3、4 步，说出 \(d\) 次幂在哪里被抵消。
返回 全书目录