数学证明一定要一步一步找到答案吗？数学家 Erdős 给出了一个奇妙的思路：我们只要能证明“随机选择有机会成功”，就能证明答案一定存在。泡杯咖啡，让我们一起欣赏这些艺术般的证明吧。

作者：silverxz
审核：phy东西

Paul Erdős图像来源：zbmath

Paul Erdős 不算是那种家喻户晓的数学家，但在数学界内部无人不知无人不晓。他的确是一位传奇数学家，建树颇多、涉猎广泛，在数论、集合论、分析、几何等领域也各有不凡的成果，在组合数学领域的地位更是无可动摇。

有许多他的逸闻趣事可以聊，比如他独特的生活方式和研究数学的方式、他才华横溢的种种体现……读者也可以在其他地方了解到，但那些不是我们今天的主题。我们今天打算介绍的是 Erdős 发扬的一种非常有趣的数学技巧，叫做概率方法 (probabilistic method).

你可能感到困惑：这是概率论里的什么方法吗？为什么说得这么笼统、这么模糊？

请不要误解，概率方法不是概率论里面的方法，概率方法的思路是：对一个与概率无关的确定性问题，人为引入一些构造出的概率结构，用概率论工具去分析它，得到一个概率相关的结果，再基于此得到原本想要的确定性的结果。也可以说，概率方法是“在非概率问题中引入概率结构解决问题”的一种方法，这里的概率完全是解决问题的脚手架，就像是平面几何的辅助线一样。

但这就是它神奇的地方。一个与概率无关的问题，怎么能引入概率呢？那真的有用吗？

这篇文章中，我们就介绍几个有趣的小例子，看一看这一方法究竟是如何起到作用的。人们通常认为，Erdős 的概率方法是组合数学领域的一种方法。但事实上，这种方法的应用远远不限于组合数学。接下来我也会选取各个领域的例子，这些例子都是甜点级的，不会有太大的阅读负担。虽然总篇幅较长，但这是讲得较细的缘故，实际阅读速度会比通常的数学类文章快上不少。

不过，读者最好具备基本的线性代数知识和初等概率知识。在此基础上，数学功底越好，阅读体验当然也就越“轻松休闲”。理想情况下，你可以在一两个闲暇的午后，泡一杯咖啡，轻松愉悦地游览过这些例子。愿它们能让你再次感受到数学之美。

向量平衡：概率方法的基本框架

我们先从一个特别简单的例子开始，解释“在非概率问题中引入概率结构”的意思。

设有 $n$ 个向量 $v_1,\dots, v_n \in \mathbb{R}^d$ ，符号 $\Vert v\Vert$ 表示向量 $v$ 的长度。试证明：存在符号 $\varepsilon_i\in\{-1, 1\}$ , 使
$\left\|\sum_{i=1}^n\varepsilon_i v_i\right\|^2\leq\sum_{i=1}^n\|v_i\|^2.$

这是一个通过调整系数 $\varepsilon_i$ 来平衡向量，使平衡后的向量 $\sum_{i=1}^n\varepsilon_i v_i$ 的长度尽可能小的问题。稍加思考后，读者应当不难发现命题背后的几何直观：想象 $\mathbb{R}^d$ 中的两个向量，当两向量的夹角是钝角时，它们合成的向量就比较短；当夹角是锐角时，合成的向量就比较长。所以只需要调整系数，让每个向量和之前向量合成的结果不要呈锐角就可以了。

向量之间的夹角关系是通过点乘结果的正负来判断的，为了写得更清楚，我们把两个向量 $x,y$ 的点乘记作 $\langle x, y\rangle$ 。记前 $k-1$ 个向量合成后的结果是

$S_{k-1}=\sum_{i=1}^{k-1}\varepsilon_i v_i.$

在 $\varepsilon_k=\pm 1$ 中选择一个使 $\varepsilon_k\langle S_{k-1},v_k\rangle\leq 0$ 的 $\varepsilon_k$ ，这就是调整系数的部分。于是

$\begin{aligned} \|S_k\|^2 &=\|S_{k-1}\|^2+\|v_k\|^2 +2\varepsilon_k\langle S_{k-1},v_k\rangle\\ &\leq \|S_{k-1}\|^2+\|v_k\|^2. \end{aligned}$

再使用归纳法即可证明原命题。

但是想必读者会有别的困惑：概率方法去哪了？这么一个含义明确、证明简短的简单命题，难道还能有其他的证明方法吗？我们这就来介绍它。

将 $\varepsilon_i$ 视为是 $\{-1, 1\}$ 上独立均匀随机变量，注意向量长度的平方就是向量和自己的点积，于是

$\mathbb E\left\|\sum_i\varepsilon_i v_i\right\|^2 = \mathbb E\left\langle\sum_i\varepsilon_i v_i, \sum_j\varepsilon_j v_j\right\rangle = \mathbb E \sum_{i,j}\varepsilon_i\varepsilon_j \langle v_i,v_j\rangle = \sum_i\|v_i\|^2.$

最后一个等号是由于 $\varepsilon_i$ 之间相互独立，对于 $i\neq j$ 有 $\mathbb{E} \left[\varepsilon_i\varepsilon_j\right]=0$ ，对于 $i=j$ 则有 $\mathbb{E}\left[\varepsilon_i\varepsilon_j\right]=\mathbb{E}\left[\varepsilon_i^2\right]= 1$ .

这两个证明几乎“同样简单”，但是方法却截然不同。后者展示了概率方法的基本框架：第一步，先把确定性的问题随机化，令 $\varepsilon_i$ 是随机变量。第二步，用概率工具去分析它，这里我们求期望并利用独立性直接方便地干掉了所有 $i\neq j$ 的交叉项。然后最后一步，再把关于概率的结果落实成确定性的结果，通常就是通过类似我们这里的“不可能所有值都比平均值更大”这样的近乎平凡的论证来断言确实存在那样一个值，而这个存在性就完全是一个确定性的结果了，与之前附加的概率结构不再有关。

可是……可是……谁会想到用这种方法解决问题呢？这甚至不只是“这种方法怎么会管用”的问题，而是“他怎么会想到这玩意呢”的问题。通常，一份合格的数学教育材料不应该仅仅展示证明，而是分析它的动机与技巧，帮助学生能掌握它、在更广阔的情境下应用它；然而正如标题所写和前文所述，本文的定位是一份下午茶读物，并不打算承担太多教育职能，我宁愿你把它当做《笑林广记》的一篇去读。我们只是领略这些例子与证明，不会深入探讨这些证明的动机、扩展等等。

随机平移与单位圆盘覆盖

第二个例子是日本的“谜题作家”稻叶直贵在 2008 年提出并解决的一个问题：

试证明：平面内任意给定的 10 个点，都可以用若干个两两不相交的单位圆盘（半径为 $1$ 的圆盘）覆盖。

注意，本节中的“不相交”均指的是圆盘内部不相交。圆盘相切的情况不视为相交，是允许的。

这个问题乍一看很难入手。可以想象，如果点数足够多，那么可能可以构造出一种结构：当我们放置一些圆盘、覆盖住一些点之后，剩余的点恰好就卡在圆盘之间的缝隙里，使我们只要用圆盘覆盖它，就必须和其他圆盘重叠。如果试图通过逐个摆放圆盘来证明这个命题，就必须证明上述情况可以被妥善处理，这无疑非常困难。

来看看概率方法是怎么做的。考虑只用固定的、有规律的模式来摆放圆盘，这虽然让摆放方式更受限，但也更容易分析。最容易想到的摆放方式当然就是在所有偶数格点上摆放。我们在所有坐标形如 $(2a, 2b)$ 的点处摆放一个单位圆盘，其中 $a, b\in \mathbb{Z}$ . 这样，平面就变成了下图的样子。

这当然不是最终的覆盖策略。如果机械地采用这个策略，那它永远无法覆盖到星型的圆盘间隙。所以我们随机地将这些圆盘共同平移一个向量 $v=(x, y)$ ，也就是说，每个圆盘的圆心横坐标增加 $x$ ，纵坐标增加 $y$ . 注意，向量 $v$ 是随机选取的，但是所有圆盘会平移相同的向量 $v$ ，而不是各自随机。

由于圆盘放置得非常有规律，呈现周期性，所以横向平移 $x$ 和平移 $x+2$ 没有区别；纵向也同理。考虑到这一点，我们假设 $v$ 均匀随机地取自一个 $2\times 2$ 的正方形 $\{(x, y): 0\leq x,y\leq 2\}$ .

更进一步，由于位置关系是相对的，随机移动所有圆盘和随机移动要覆盖的点也并没有区别。上述过程等价于把平面上要覆盖的点反向平移 $v$ ，如果平移后落在某个圆盘中，则它会被覆盖到；否则就没有被覆盖。由于平移的向量 $v$ 均匀随机地取自 $2\times 2$ 正方形，所以平移后的点也均匀随机地分布在某个 $2\times 2$ 正方形中，它会被覆盖的概率就是这一正方形与圆盘相交的面积占比。如果平移后的点均匀分布在下图的一个正方形中，它被覆盖的概率就是蓝色部分的面积除以整个正方形的面积 $4$ .

然而，不论这个 $2\times 2$ 正方形处于什么位置，它与圆盘相交的面积总是相同的。这是因为前面说过的：圆盘的分布在横纵方向都以 $2$ 为周期。想象我们平面上滑动这个 $2\times 2$ 正方形，从一侧滑出去的部分又会从另一侧完全相同地滑进来，所以与圆盘相交的总面积不会改变。我们只需计算上图左侧最规整的情况，与圆盘相交的总面积是 $\pi$ ，由四个 $1/4$ 圆组成，占据整个正方形的 $\pi /4$ .

总而言之，这说明：若我们把所有圆盘同时随机平移 $v$ ，那么平面上一点会被某个圆盘覆盖的概率是 $\pi / 4$ .

基于这一事实，概率方法已经可以给出一个较弱的结果：平面上任意给定的 $4$ 个点都可以用若干个两两不相交的单位圆盘覆盖。考虑上述随机平移，单个点被覆盖的概率是 $\pi / 4$ ，所以这四个点被覆盖的期望个数是

$4\times \frac{\pi}{4} = \pi > 3$

读者可能对为什么我们可以把 $4$ 和概率 $\pi/4$ 乘起来计算期望有疑惑。为了照顾到这部分读者，我们把它仔细拆解一下，已经熟悉这部分概率论技术的读者可以跳过。这里用到的技术叫做“指示器随机变量”。设 $I_1$ 表示第一个点在圆盘随机平移后有没有被覆盖，若被覆盖，则 $I_1=1$ ；若没有被覆盖，则 $I_1=0$ 。这是一个随机变量，它指示了第一个点有没有被覆盖，所以叫“指示器随机变量”。类似地，定义 $I_2, I_3, I_4$ 表示第二、第三、第四个点有没有被覆盖。此时，随机平移后覆盖了的点的数量就是这四个随机变量的加和，也是一个新的随机变量

$X = \sum_{i=1}^4 I_i$

所以覆盖点数的期望就是 $\mathbb{E}[X]=\mathbb{E}[\sum_{i=1}^4 I_i]$ ，由于期望是线性的，求和可以拿到期望外面来，所以

$\mathbb{E}[X] = \sum_{i=1}^4 \mathbb{E}[I_i]$

对于 $\mathbb{E}[I_i]$ ，只需要通过定义计算 $\mathbb{E}[I_i] = 1\times \frac{\pi}{4} + 0\times \left(1-\frac{\pi}{4}\right)=\frac{\pi}{4}$ ，因此

$\mathbb{E}[X]=4\times \frac{\pi}{4} = \pi.$

这就是上述计算的细节拆解。注意， $I_i$ 之间当然不是独立的，但是期望的线性允许我们在计算期望的时候简单把它们加起来，并不需要独立。读者在后面的例子还会继续见到这种方法。总而言之，期望覆盖的点数是 $\pi > 3$ .

这意味着，存在一个平移 $v$ 使之覆盖超过 $3$ 个点——否则期望应该小于等于 $3$ 才对。覆盖的点数只能是整数，所以“超过 $3$ 个点”就说明覆盖了全部 $4$ 个点，也就证明了这个更弱的命题。

可是，我们要证明的原命题不是 $4$ 个点，而是 $10$ 个点，这怎么办呢？注意到，这一方法所利用的仅仅是圆盘排列的周期性。在保证这种周期性的前提下，如果能让圆盘排列得更密，使上述的 $\pi/4$ 概率可以变成更大的数字，那么概率方法就可以给出更好的答案。所以我们考虑一种更密的排列，它呈现下图的蜂窝状结构，仍然有两个周期方向，一个是水平的，另一个与水平方向成 $60$ 度角。

此时，周期性仍然存在，当我们滑动这一平行四边形时，它与圆盘相交的面积仍然保持不变。读者可以看出，这个面积仍然是整个圆的面积 $\pi$ ，因为平行四边形与圆盘相交的部分可以如图拼凑成整个圆。但是面积占比变了，因为平行四边形的面积只有 $2\sqrt 3$ ，面积占比为 $\frac{\pi}{2\sqrt 3}$ .

我们还是考虑把所有圆盘随机平移一个向量 $v$ ，但这次， $v$ 均匀随机地取自上图的平行四边形。这样，单个点被圆盘覆盖的概率就是 $\frac{\pi}{2\sqrt 3}$ ，10 个点被覆盖的期望个数就是

$10\times \frac{\pi}{2\sqrt 3} \approx 9.07 > 9$

同样，这就意味着存在一种平移方式，使得圆盘可以覆盖超过 $9$ 个点——也就是覆盖了全部 $10$ 个点，于是也就完成了证明。

我们用这种新的排列方式证明了可以覆盖 $10$ 个点的结果。那么，能换更密集的排列来证明更强的结果吗？不能了，因为上述的蜂窝状结构已经达到了平面上不相交单位圆堆积的最大密度，不存在更密的排列方式了，这叫做 Thue 定理。

不过，确实还能证明更强的结果。Greg Aloupis 等人证明了 $12$ 个点的情况仍然成立。但那不是“换个排列、照搬现有方法”就能直接解决的了。

至于需要多少个点才能保证无法覆盖，人类还不知道这个问题的精确答案。已经知道有 $50$ 个点的反例，但是 $12$ 到 $50$ 之间的世界，还在等待人类探索。

随机选择与图的独立集

第三个例子来自于图论，读者只需知道图的基本概念：图是一些顶点和顶点之间的边构成的对象。顶点构成的集合记作 $V$ ，边构成的集合记作 $E$ ，图记作 $G=(V, E)$ .

对于点集 $S\subset V,$ 若 $S$ 中的任意两点在图中都没有边连接，则称这样的 $S$ 为独立集，大小为 $|S|$ .

下图展示了一个例子，图就是由这样的一些点和相连的边构成的。其中，灰色顶点构成了一个独立集。这当然不是唯一的独立集。

圆点表示顶点，连接顶点的线段表示边。灰色顶点构成独立集 S。

求解图的最大独立集是图论中的经典问题。记 $n=|V|, m=|E|$ ，那么我们能否给出最大独立集大小 $\alpha(G)$ 的关于 $n, m$ 的下界估计呢？也就是说，一个 $n$ 个点 $m$ 条边的图，它的最大独立集大小 $\alpha(G)$ 至少有多大？

这个问题看起来就比上一个问题棘手多了。图的结构是任意的，若想要做下界估计，那些最“坏”的结构会妨碍你。可最坏的结构长什么样？……沿着这样的思路想下去，似乎难以避免一头扎进深邃的图论世界中。但是我们可以换个思路，看看概率方法怎样漂亮地给出一个估计。

我们让每个顶点独立地以概率 $p$ 被选入集合 $S$ . 设 $X=|S|$ 是被选入的点数，而 $Y$ 是被选入的这些点之间连了多少条边。 $X,Y$ 都是随机变量。

当 $Y=0$ 的时候， $S$ 就是独立集了；否则它就不是。我们当然希望它是独立集，这样我们才能使用概率方法的后续操作，给出“存在一个大小为 $\dots$ 的独立集”这样的结果。那怎么办呢？这里的做法被称为 alteration method, 也就是“删改法”：如果概率方法添加的概率结构不能直接给出我们想要的对象，那么就删删改改让它变成我们想要的。如果 $S$ 不是独立集，那把它调整成独立集就好了。

对于 $S$ 中的 $Y$ 条边，任意选择每条边的一个端点，把选择的至多 $Y$ 个点（注意有可能有重复的，所以是至多）从 $S$ 中删去，得到的集合 $S'$ 一定是独立集。这样我们就得到了不小于 $X-Y$ 的独立集，注意若 $X<Y$ 也没有关系，这仍然是一个成立的平凡下界。

接下来就像之前做的那样，取期望，计算 $\mathbb{E}[X-Y]$ . $\mathbb{E}[X]=pn$ 可以直接得到，那么 $\mathbb{E}[Y]$ 怎么算呢？可以使用上一个例子用过的“指示器随机变量”技术来完成。设随机变量 $I_e$ 在边 $e$ 被选中时取值为 $1$ ，在没有被选中时取值为 $0$ 。这样，我们就可以利用期望的线性把它分解

$\mathbb{E}[Y] = \sum_{e\in E} \mathbb{E}[I_e]$

$\mathbb{E}[I_e]$ 的值就是边 $e$ 被选中的概率。而对于边 $e$ 来说，它被选中当且仅当它两端的顶点都被选中，由于顶点的选择是独立的，这个概率就是 $p^2$ . 因此 $\mathbb{E}[I_e]=p^2$ ，这样就得到了 $\mathbb{E}[Y]=p^2m$ ，再代入也就得到了

$\mathbb E[X-Y]=pn-p^2m.$

这也就说明了至少有一个独立集不小于 $pn-p^2 m$ ，即 $\alpha(G)\ge pn-p^2m$ . 注意 $p$ 是我们指定的，可以按照 $n,m$ 选取最好的 $p$ . 当 $m > 0$ 时，将它视为是一个关于 $p$ 的二次函数，最大值在 $p=\frac{n}{2m}$ 处取到，再考虑到 $p\in [0, 1]$ 的概率取值约束和 $m=0$ 的边界情况，答案是以下的分段结果

$\alpha(G)\ge\begin{cases} n-m, & m\le \dfrac n2,\\[6pt] \dfrac{n^2}{4m}, & m\ge \dfrac n2. \end{cases}$

也不算复杂，是不是？但问题是，这个界足够好么？

虽然许多时候概率方法能带来神奇的结果，但我们没有理由期待它永远是灵丹妙药，用出来结果就是好的。结果好不好，当然也取决于问题本身的性质以及方法的使用方式。我们刚才给出的结果不算糟糕，但也不算特别好。这种做法还是太粗暴了。

考虑另一种不同的概率方法：把所有顶点随机排列。随机排列后，对于每个顶点 $v\in V$ ，若 $v$ 在排列中的次序比所有和它相邻的顶点都更靠前，就把 $v$ 加入集合 $S$ . 这个做法简洁而优美，可以看到，这样得到的 $S$ 已经是独立集，因为一条边中的两个点只有排序靠前的那个有可能会被选到 $S$ 里，这就保证了 $S$ 中的任意两点之间都没有边相连。

和之前类似，对每个顶点 $v\in V$ 定义指示器随机变量 $I_v$ 表示它是否被选入 $S$ ，则 $\mathbb{E}|S|=\sum_{v\in V}\mathbb{E} [I_v]$ . 而一个点是否会被选入 $S$ ，与那些和它相连的顶点相关。设 $d(v)$ 是图中与点 $v$ 相连的顶点的数量，由于 $v$ 和这 $d(v)$ 个点谁排在最前完全是等概率的，所以 $v$ 被选中（当且仅当 $v$ 在这 $d(v)+1$ 个点中排在最前）的概率是 $1/(1+d(v))$ . 因此

$\mathbb{E}|S|= \sum_{v\in V}\frac1{1+d(v)}.$

同样，既然期望都等于这个量，那么就至少有一个独立集大小不小于这个量，因此

$\alpha(G)\ge \sum_{v\in V}\frac1{1+d(v)}.$

这个结果不弱于刚才的结果，在许多情况下还要强许多。证明这件事只需要做一个分类讨论，利用一下 Cauchy 不等式；但本文不预设读者知道 Cauchy 不等式，且这个证明偏离了本文中心，所以就不证了。总而言之，我们得到了一个新的、更好的结果，这个结果重要到足以有一个名字，叫做最大独立集的 Caro-Wei bound.

我们不做深入的剖析，对图论本身感兴趣或者有一定了解的读者可以尝试分析这两种方法产生差异的更根本的原因，尝试找一找是哪些情形让前一种方法给出的估计更松，而后一种方法是如何规避掉那些损失的。但在这里，读者只需要看到以下事实：如果你用出了“概率方法”，它或许可以给你一个结果，但它当然不自动保证你会获得一个足够好的结果，你设计的概率结构越适合这个问题，获得的结果才越好。

随机抽样与近似 Carathéodory 定理

与图论有关的例子还有很多，比如 Ramsey 数（也是最常被提到的例子）等图染色相关的问题。但是那些例子常常不太简洁，我们就只讲刚才那一个图论的例子，接下来去其他领域转转。

下面这个例子来自高维概率的教材《高维概率》(High-Dimensional Probability by Roman Vershynin).

读者需要先知道凸组合和凸包的概念。 $m$ 个点 $z_1,\dots,z_m\in \mathbb{R}^n$ 的凸组合就是系数非负、总系数之和为 $1$ 的线性组合，即，若 $\lambda_i\geq 0$ 且 $\sum_{i=1}^m \lambda_i = 1$ ，则称 $z = \sum_{i=1}^m\lambda_i z_i$ 是 $z_i$ 的凸组合。如果读者不了解，可以在 $\mathbb{R}^2$ 平面上想象：两个点的凸组合就是这两个点连成的线段上的点。

更进一步，集合 $T\subset \mathbb{R}^n$ 的凸包 $\operatorname{conv}(T)$ 是 $T$ 中任意有限多个元素的凸组合构成的集合。

实际上，“任意有限多个”在这里可以被替换成“不超过 $n+1$ 个”，这是因为经典的 Carathéodory 定理。

(Carathéodory 定理). 设 $T \subset \mathbb{R}^n$ ，则任何凸包中的点 $x\in \operatorname{conv}(T)$ 都能表达为 $T$ 中不超过 $n+1$ 个点的凸组合。

这个证明不难，但是不怎么好玩。我们不去证它，后面也不会用，感兴趣的读者可以自行搜索。我们提到它的原因是想要考虑它的扩展问题：如果我们不得不使用更少的点做凸组合，我们可能不能得到凸包中的所有点，但是我们能在多大程度上逼近凸包中的点呢？这个问题的答案是另一个定理。

(近似 Carathéodory 定理). 设 $T \subset \mathbb{R}^n$ ，其中任意两点之间的距离不超过 $1$ ，则对于凸包中的点 $x\in \operatorname{conv}(T)$ 和正整数 $k$ ，一定能找到点 $x_1, \dots, x_k\in T$ （允许重复），使
$\left\Vert x-\frac 1 k \sum_{j=1}^k x_j\right\Vert \leq \frac {1}{\sqrt k}$

它的意思是，我们总能找到 $T$ 中的 $k$ 个点，用它们的平均值来逼近 $x$ ，逼近效果还不会太差，欧氏距离上只有 $1/\sqrt k$ 的误差。这个结果好到令人惊讶，我们没控制 $T$ 的形状，它可以很奇怪，但是我们竟然能证明出一个非常稳定的逼近速率，并且与 $n$ 无关，甚至还只使用了“取平均值”这种最特殊的凸组合。接下来我们看看这是怎么证明的。

不妨取 $T$ 中一点作为新的坐标原点，这样 $T$ 就可以被以原点为球心、半径为 $1$ 的单位球给包住了，其中元素的模长都不超过 $1$ .

对于 $x\in \operatorname{conv}(T)$ ，设它可以写成 $m$ 个元素 $x_1, \dots, x_m\in T$ 的凸组合，系数记作 $\lambda_i$ . 我们打算就直接用这 $m$ 个元素中的 $k$ 个来逼近 $x$ ，但是不是确定性地做，而是随机去做。设 $k$ 个独立同分布的随机变量 $Z_j(j=1,\dots,k)$ 以 $\lambda_i$ 的概率取值 $x_i$ 。由定义，

$\mathbb{E}[Z_j] = \sum_{i=1}^m \lambda_i x_i = x$

所以我们用 $\frac 1 k \sum_{j=1}^k Z_j$ 来逼近 $x$ ，就像大数定律那样。接下来计算我们想要控制的逼近误差，不过实际上是计算平方，因为那更好计算

$\mathbb{E} \left\Vert x-\frac 1 k \sum_{j=1}^k Z_j\right\Vert^2 = \frac 1 {k^2} \mathbb{E} \left\Vert \sum_{j=1}^k (Z_j-x)\right\Vert^2 = \frac 1 {k^2} \sum_{j=1}^k \mathbb{E} \left\Vert Z_j-x\right\Vert^2$

第二个等号只是简单地把平方展开了，由于 $Z_j-x$ 之间独立且期望为 $0$ ，交叉项的期望被消掉了，我们在第一个例子中看过类似的事情发生。于是问题变成了计算 $\mathbb{E} \left\Vert Z_j-x\right\Vert^2$ ，这里下标 $j$ 的取值不重要，因为所有 $Z_j$ 分布相同，不管 $j$ 取什么，这个式子的值都是一样的。只需要用简单的放缩来给出上界：

$\mathbb{E} \left\Vert Z_j-x\right\Vert_2^2 = \mathbb{E}\Vert Z_j\Vert^2 - \Vert \mathbb{E} Z_j\Vert^2\leq 1-\Vert x\Vert^2 \leq 1$

这是因为我们刚才说过的，元素的模长不超过 $1$ . 这样就得到了

$\mathbb{E} \left\Vert x-\frac 1 k \sum_{j=1}^k Z_j\right\Vert^2 \leq \frac 1 k$

而这意味着，一定存在 $Z_j$ 的一组取值 $z_j\in T$ 使

$\left\Vert x-\frac 1 k \sum_{j=1}^k z_j\right\Vert^2 \leq \frac 1 k$

开根号就得到了要证的结果。

这也是非常经典的证明。这里的方法也被称为 Maurey 经验方法，但我想，它和 Erdős 概率方法的精神没有本质区别。

随机矩阵与线性码

最后一个例子属于编码领域。它会有点长，但不是因为它很困难，而是因为我们得先介绍不少基本设定。

一些长度为 $n$ 的 01 字符串构成的集合 $C\subset \{0, 1\}^n$ 称为长度为 $n$ 的二元码，其中的元素称为码字。

两个 $n$ 位 01 字符串之间不同的位的数量称为它们的 Hamming 距离，记作 $d_H$ . 比如 $x=(0, 0, 1, 1, 0)$ 与 $y=(1, 0, 1, 1, 1)$ 的 Hamming 距离是 $d_H(x,y)=2$ ，因为只有首位和末位不同。

定义二元码 $C$ 的最小 Hamming 距离 $d(C)$ 是其任意两个码字能产生的最小 Hamming 距离，即

d(C)=\min_{\substack{x,y\in C\\x\neq y}}d_H(x,y).

以下简称 $d(C)$ 为 $C$ 的 Hamming 距离，省略“最小”二字。

可以看出：Hamming 距离越大，就说明码字之间的差异越大，这在通信中就更有利于纠正传输错误。

但是在固定 $n$ 的情况下，随着 $C$ 的规模 $|C|$ 增大，它所能拥有的 Hamming 距离 $d(C)$ 通常会降低。因为规模增大让码字难以有更大的差异，使它们“挤在一起”。最极端的情况下，若 $C=\{0,1\}^n$ 包含所有 01 字符串，那它的 Hamming 距离就是 $1$ .

我们希望在保证一定的 Hamming 距离 $d$ 的前提下，寻找规模尽可能大的二元码 $C$ ，因为规模大意味着码率高、冗余少。所以问题就是：

给定码字长度 $n$ 和希望达到的距离 $1\leq d\leq n$ ，若要求二元码 $C$ 满足 $d(C)\geq d$ ，则 $|C|$ 至少能有多大？

它的精确答案并不容易给出。在这里，我们只想找到一个相对满意的下界，也就是“至少能找到那么大的 $C$ ”。这个问题还不需要请出概率方法，先看一个精彩的体积论证。

我们尝试往一个空的集合里不断添加码字，每次添加的码字必须和已有的所有码字都有至少 $d$ 位不同，也就是有至少 $d$ 的 Hamming 距离。这样重复添加，直到加不进去为止，得到二元码 $C$ .

这时，任何一个没有被添加的 01 字符串 $y$ ，都一定与某个码字 $x\in C$ 至多只有 $d-1$ 位不同，即 $d_H(x, y)\leq d-1$ . 因为，如果它与所有码字都有 $d$ 位以上不同，那它就可以被加入到 $C$ 中，与“直到加不进去为止”矛盾。

我们记与 $x$ 的 Hamming 距离不超过 $d-1$ 的所有串构成的集合为 $B(x, d-1)\subset \{0, 1\}^n$ . 上一段说的事情就是，每个 $y\in \{0, 1\}^n$ 一定存在于某个 $B(x, d-1)$ 中，其中 $x\in C$ ；反过来说，所有 $B(x, d-1)$ 覆盖了整个 $\{0, 1\}^n$ ，即

$\bigcup_{x\in C} B(x, d-1) = \{0, 1\}^n$

注意集合 $B(x, d-1)$ 的大小与 $x$ 无关，记作 $V_n(d-1)$ 。等式左侧集合的元素数量至多为 $|C|\cdot V_n(d-1)$ ，所以如果上述覆盖成立，那么必须得有

$|C|\cdot V_n(d-1) \geq 2^n$

从而这样构造的 $C$ 满足

$|C| \geq \frac{2^n}{V_n(d-1)}$

这样，我们就给出了刚才那个问题的一个简明下界：最大的 $C$ 至少有 $\frac{2^n}{V_n(d-1)}$ 那么大。这里的 $B(x, d-1)$ 其实就是在 Hamming 距离意义下，以 $x$ 为中心、以 $d-1$ 为半径的“球”，我们刚才就是在算至少需要多少个球的体积才能填满整个空间，所以这种经典方法被称作“体积论证”，这类方法也被广泛应用于其他问题中。

体积 $V_n(d-1)$ 当然是可以算的，不妨考虑 $B(0, d-1)$ 的大小，就是至多 $d-1$ 个 $1$ 的 01 串，因此就是组合数的累加 $\sum_{j=0}^{d-1}\binom n j$ ，如果你想，也可以把它代进上面的式子。通信领域常常用一个关于熵的不等式做这个式子的后续估计，但我们这里没有这样做的必要，就保留这个形式不去管它。

好啦，这个例子涉及到概率方法的部分从这里才开始。现在我们不仅希望二元码有尽量大的规模和尽量大的 Hamming 距离，还希望它有一定的结构：由一个矩阵统一产生。这样的码叫线性码，下面我们来定义它。

从现在开始，我们不仅把 $0,1$ 看成字符，还看成可以加减的数字，并且要求加法模 $2$ 计算，即

$1+1 = 0$

取一个 $k\times n$ 的 01 矩阵 $G$ ，它可以把长度为 $k$ 的 01串 $u\in \{0, 1\}^k$ 编码为 $uG\in \{0, 1\}^n$ . 注意，矩阵乘法中涉及到的计算也都是模 $2$ 进行的，所以得到的结果还是一个 01 串，长度为 $n$ .

称所有编码结果构成的集合

$C=\{uG: u\in \{0, 1\}^k\}\subset \{0, 1\}^n$

为一个线性码。

线性码比一般的二元码多了额外的代数结构，它可以通过一个矩阵乘法来编码，是编码、通信领域中很基本的研究对象。所以我们很想把刚才的问题增加要求，变成线性码的版本：

给定码字长度 $n$ 和希望达到的距离 $1\leq d\leq n$ ，若要求线性码 $C$ 满足 $d(C)\geq d$ ，则 $|C|$ 至少能有多大？试给出一个下界。

这种情况下，之前的体积论证不再容易奏效，因为它难以保证构造出的 $C$ 确实是个线性码。不是不行，但是不容易——至少不太容易放在这里轻松愉快地阅读。于是我们就要请出概率方法了，在此之前，我们先看看线性码本身的性质，这会让 Hamming 距离的计算可以被化简。

首先注意到，如果我们做模 $2$ 的运算，那么 $x,y$ 之间的 Hamming 距离恰恰就是 $x+y$ 中 $1$ 的个数——学计算机的同学会发现，这里的加法其实就是二进制串的异或，相同为 $0$ 不同为 $1$ ，因此 $1$ 的个数就是不同的位的数量，也就是 Hamming 距离。我们给“01串 $z$ 中 $1$ 的个数”起一个新名字，叫做 $z$ 的 Hamming 重量 $w_H(z)$ .

由于线性码是被矩阵 $G$ 用乘法生成的，对于码字 $uG, vG$ 而言，其加和 $uG+vG=(u+v)G$ 还是一个码字，所以我们可以转写 $C$ 的 Hamming 距离的定义为

$d(C)=\min_{z\in C\setminus \{0\}} w_H(z)$

这是因为，不同 $uG,vG\in C$ 的 Hamming 距离就是 $z=(u+v)G\neq 0$ 的 Hamming 重量 $w_H(z)$ ；而对于 $z\in C\setminus\{0\}$ ，其 Hamming 重量又是 $z$ 自己和 $0\in C$ 的 Hamming 距离 $d_H(z, 0)$ . 所以两个定义等价。如果我们希望让 Hamming 距离不小于 $d$ ，只需要求其中每个非零码字的 Hamming 重量不小于 $d$ 即可。

得到这一重要性质之后，就可以请出我们的概率方法了。

随机取矩阵 $G$ ，令其中的每一项是独立均匀的 01 随机比特。此时，对于确定的非零 $u\in \{0, 1\}^k$ ，可以发现 $uG$ 是长度为 $n$ 的均匀随机 01 串，每一位是独立均匀的 01 随机比特。这是因为， $uG$ 的每一位都等概率地取 $0$ 或 $1$ ，而且每一位都由 $G$ 中不同的列决定，所以位之间相互独立。

而“一个随机 01 串的 Hamming 重量小于 $d$ ”这件坏事发生的概率——也就是有少于 $d$ 个 $1$ 的概率——是多少呢？和前面一样，就是组合数累加除以总数

$\Pr ( w_H(uG) < d ) = \frac{1}{2^n} \sum_{j=0}^{d-1}\binom n j$

为了看着简单，我们还是把分子记作之前的 $V_n(d-1)$ 吧，虽然这里我们不使用它“球的体积”的几何含义。

对于所有 $2^k-1$ 个非零输入串，编码后得到的码字至少有一个 Hamming 重量小于 $d$ 的概率，可以估计为

$\Pr\left( \bigcup_{u\neq 0} \{w_H(uG)< d\} \right) \leq \sum_{u\neq 0} \Pr \left( w_H(uG) < d \right) = (2^k-1) 2^{-n} V_n(d-1)$

第一个不等式是概率的 union bound $P(A\cup B) \leq P(A)+P(B)$ .

我们知道，只要这个概率小于 $1$ ，就意味着“坏事不是必然发生”，也就存在一个确定的 $G$ 使每个非零输入串 $u\in \{0, 1\}^k$ 都满足

$w_H(uG)\ge d.$

而想要使这个概率小于 $1$ ，只需要满足

$2^k \leq \frac{2^n}{V_n(d-1)}.$

也就是说，只要 $k$ 和 $n$ 满足上述不等式，就存在一个 $k\times n$ 矩阵 $G$ ，可以给出一个 Hamming 距离不小于 $d$ 的线性码 $C$ .

那么这个线性码 $C$ 的规模 $|C|$ 是多大呢？就是 $2^k$ ，因为不同的输入串 $u, v\in \{0, 1\}^k$ 一定会被 $G$ 映射到不同的结果 $uG\neq vG$ ：如果 $uG=vG$ ，那么在模 $2$ 加法下会导致 $(u+v)G=uG+vG=0$ ，使 $w_H((u+v)G)=0$ ，而 $u+v\neq 0$ 是非零串，这使 $d(C)=0 < d$ 矛盾，所以只能是 $uG\neq vG$ 。一共有 $2^k$ 个输入串，与 $G$ 相乘后会得到 $2^k$ 个不同的结果，因此 $|C|=2^k$ .

这样，我们就在条件加强成线性码的情况下，仍然给出了和体积论证几乎一样的结果（由于线性码的规模必须是 $2$ 的幂，所以可能有一点取整和常数差异）。这当然很令人满意，我们加强了条件，却几乎没有付出额外代价。

你可能觉得，会不会是因为这两个界都太松，才能发生这种几乎不需要付出代价的加强？答案是：我们不知道。这个结果还有改进空间，但人类现在还不知道一般情形下的最优二元码和最优线性码能做到多好，所以也不知道这种几乎无损的加强能否发生在最优码上。不过，这里给出的下界确实已经是编码理论中很经典、重要的基准结果，通常归入 Gilbert-Varshamov bound.

结语

我们给出了五个例子，篇幅已经不短，所以就到此打住吧。回顾这些例子，它们跨越不同的领域，共同点是都有一些允许犯错的余裕，要么是估计，要么是不等式；然而要想把这些犯错空间在确定性的证明中利用上，却不简单。这几个概率方法的证明能够在不深入涉足复杂结构的情况下，恰到好处地利用到这里的犯错空间，蜻蜓点水般地跨越障碍、给出结果，是艺术般的证明。

在艺术之外，还有技术。坦白来说，想要从这几个证明中学到可供利用的证明技术，恐怕不容易。我们看到的是已经完成的巧妙证明，却看不到它们最初是怎样被想到的。的确，其中有些证明可能是现代教学中反复迭代优化的产物，本来就不容易想到。但是也没有关系，见得多了，或许有一天也就用上了，没有必要过于功利地学习数学。愿我们每个人都仍能感受到数学的美。便以此句结束本文：