第五部　从无穷到有限

第十六章把概率切成一层一层

只问去不去电影院。假设有三种情况，助手建议去电影院的机会分别是 $\frac{1}{4}$ 、 $\frac{1}{2}$ 、 $\frac{3}{4}$ 。是哪三种情况，这里不用管。我们把它们编成顶点 $1$ 、 $2$ 、 $3$ ，“去”记作回答 $1$ ，“不去”记作回答 $0$ 。回答 $0$ 的机会就是剩下的 $\frac{3}{4}$ 、 $\frac{1}{2}$ 、 $\frac{1}{4}$ 。

先看回答 1

祺乐剪了三张纸条，拿一整张的长度当 $1$ ，三张分别长 $\frac{1}{4}$ 、 $\frac{1}{2}$ 、 $\frac{3}{4}$ ，底边对齐立在桌上，就是三根柱子。韵吉拿一把尺子平放，从桌面往上移，每越过一张纸条的顶端，就在旁边记一笔。

图 27：三个顶点的两组柱子。左边是回答 1 的机会，右边是回答 0 的机会。每一层标的是“这一层被哪些顶点共同拥有”。 — 图 27三个顶点的两组柱子。左边是回答 $1$ 的机会，右边是回答 $0$ 的机会。每一层标的是“这一层被哪些顶点共同拥有”。

最底下 $\frac{1}{4}$ 的高度，三根柱子都有，这一层属于 ${1, 2, 3}$ ；
再往上 $\frac{1}{4}$ （从 $\frac{1}{4}$ 到 $\frac{1}{2}$ ），只剩顶点 $2$ 和 $3$ 够得着，这一层属于 ${2, 3}$ ；
最上面 $\frac{1}{4}$ （从 $\frac{1}{2}$ 到 $\frac{3}{4}$ ），只有顶点 $3$ 够得着，这一层属于 ${3}$ 。

再看回答 0

回答 $0$ 的三根柱子高度是 $\frac{3}{4}$ 、 $\frac{1}{2}$ 、 $\frac{1}{4}$ 。同样横着切：最底下 $\frac{1}{4}$ 属于 ${1, 2, 3}$ ，中间 $\frac{1}{4}$ 属于 ${1, 2}$ ，最上面 $\frac{1}{4}$ 属于 ${1}$ 。

把同名的层合起来

现在不管原来是回答 $0$ 还是回答 $1$ ，只要层的集合相同，就把它们的高度加在一起。 ${1, 2, 3}$ 在两边各有 $\frac{1}{4}$ ，合起来是 $\frac{1}{2}$ ；其余四个集合各只出现一次。得到五个权重：

集合 $S$	${1, 2, 3}$	${1, 2}$	${2, 3}$	${1}$	${3}$
权重 $λ_{S}$	$\frac{1}{2}$	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{4}$

$λ$ 是希腊字母，读作“兰布达”， $λ_{S}$ 就是集合 $S$ 的权重。

这些集合，就是第十五章说的“新的类”。现在我们把它们当成新的“回答”：原来的名字（ $0$ 还是 $1$ ，去还是不去）先放到一边，只记住每一份机会被哪些顶点共享。

于是新问题是这样的：每个顶点的“回答”换成了一个包含它自己的集合，抽到这个集合的机会就是它的权重。顶点 $1$ 回答 ${1, 2}$ ，意思是它这一次用的是它和顶点 $2$ 共有的那一份机会。比如顶点 $1$ 可能的回答是 ${1, 2, 3}$ 、 ${1, 2}$ 、 ${1}$ ，机会分别是 $\frac{1}{2}$ 、 $\frac{1}{4}$ 、 $\frac{1}{4}$ ，加起来正好是 $1$ 。顶点 $2$ 可能的回答是 ${1, 2, 3}$ 、 ${1, 2}$ 、 ${2, 3}$ ，加起来也是 $1$ 。顶点 $3$ 同样。

你可能注意到，五个权重全部加起来是 $\frac{1}{2} + 4 \times \frac{1}{4} = \frac{3}{2}$ ，不是 $1$ 。这没有关系。这五个数不是同一个签盒里的五种签，每个顶点只用到包含它自己的那三层。我们要求的是，对每个顶点，把所有包含它的集合的权重加起来，恰好是 $1$ 。

距离有没有变

验证第一条规矩。原来顶点 $1$ 和 $2$ 回答 $1$ 的机会差 $\frac{1}{4}$ ，回答 $0$ 的机会也差 $\frac{1}{4}$ ，全变差距离是 $\frac{1}{4}$ 。

在新问题里，顶点 $1$ 和 $2$ 都有 ${1, 2, 3}$ 和 ${1, 2}$ 这两个集合，权重完全相同，不产生差别。差别只在于：顶点 $1$ 有 ${1}$ （权重 $\frac{1}{4}$ ）而顶点 $2$ 没有；顶点 $2$ 有 ${2, 3}$ （权重 $\frac{1}{4}$ ）而顶点 $1$ 没有。两个差加起来是 $\frac{1}{2}$ ，除以 $2$ ，还是 $\frac{1}{4}$ 。

一般地，对每一种原来的回答，把各个顶点的柱子从矮到高排好，两根柱子的高度差，正好等于“只有其中一根够得着”的那些层的厚度之和。把所有回答加起来，全变差距离就原样保留下来了。

多走一步：切层的统一公式

设原来的回答是 $a$ ，顶点 $v$ 回答 $a$ 的机会是 $μ_{v} (a)$ （ $μ$ 是希腊字母，读作“缪”）。对一个非空的顶点集合 $S$ ，它在回答 $a$ 上分到的层的厚度是 $h_{S} (a) = [v \in S min μ_{v} (a) - v \in / S max μ_{v} (a)]_{+}$ 其中 $v \in S$ 读作“ $v$ 属于 $S$ ”， $v \in / S$ 读作“ $v$ 不属于 $S$ ”。整个式子的意思是： $S$ 里最矮的柱子，减去 $S$ 外最高的柱子；如果结果是负数，就记作 $0$ （方括号右下角的加号就是这个意思）；如果 $S$ 外面没有顶点，减去的数记作 $0$ 。只有当 $S$ 恰好是“高度不低于某条线的所有顶点”时，这个厚度才可能是正的，这正是我们横着切出来的那些层。集合 $S$ 的权重就是它在所有回答上的厚度之和： $λ_{S} = \sum_{a} h_{S} (a)$ 。

图 28：切层以后，每个顶点的“回答”是一个包含它自己的集合，每根柱子的总高都是 1；相邻两根柱子只有一层不同，厚 1/4。 — 图 28切层以后，每个顶点的“回答”是一个包含它自己的集合，每根柱子的总高都是 $1$ ；相邻两根柱子只有一层不同，厚 $\frac{1}{4}$ 。

怎样变回原来的回答

验证第二条规矩。新问题抽出来的是集合，原问题需要的是 $0$ 或 $1$ 。怎样变回去？

对每个集合，我们记下它的权重里，有多少来自回答 $0$ ，有多少来自回答 $1$ 。

${1, 2, 3}$ 的权重 $\frac{1}{2}$ 里，一半来自回答 $0$ ，一半来自回答 $1$ ；
${1}$ 和 ${1, 2}$ 全部来自回答 $0$ ；
${3}$ 和 ${2, 3}$ 全部来自回答 $1$ 。

抽完集合以后，对每一个被抽到的集合，再按这个比例抽一次原来的回答，而且所有抽到同一个集合的顶点共用这一次的结果。比如抽到 ${1, 2, 3}$ 的顶点，一起看同一枚硬币，正面都回答 $1$ ，反面都回答 $0$ ；抽到 ${1}$ 或 ${1, 2}$ 的回答 $0$ ，抽到 ${3}$ 或 ${2, 3}$ 的回答 $1$ 。

拿顶点 $2$ 核对一下。它抽到 ${1, 2, 3}$ 的机会是 $\frac{1}{2}$ ，这时有一半回答 $1$ ；抽到 ${2, 3}$ 的机会是 $\frac{1}{4}$ ，这时一定回答 $1$ ；抽到 ${1, 2}$ 时回答 $0$ 。所以它回答 $1$ 的机会是 $\frac{1}{2} \times \frac{1}{2} + \frac{1}{4} = \frac{1}{2}$ ，和原来一样。顶点 $1$ 和 $3$ 也能这样核对出 $\frac{1}{4}$ 和 $\frac{3}{4}$ 。

两个顶点如果在新问题里抽到了同一个集合，用的是同一次抽签的结果，变回去以后回答一定相同。抽到不同的集合，变回去以后还可能碰巧相同，比如顶点 $1$ 抽到 ${1}$ 、顶点 $2$ 抽到 ${1, 2}$ ，两个都回答 $0$ 。所以，“两端不同”的机会只会减少，不会增加。

两条规矩都做到了。

多走一步：一般的变回去

一般地，集合 $S$ 的权重，是它在各种回答上分到的层的厚度加起来（见上面的“切层的统一公式”）。变回去时，抽到 $S$ 的顶点按这些厚度占权重的比例，一起抽一个回答。对一个顶点来说，把包含它的各个集合在回答 $a$ 上的厚度加起来，正好是它在回答 $a$ 上那根柱子的全部高度，所以它回答 $a$ 的机会和原来一样（附录三第四节的第一个等式）。两个顶点回答不同，只可能发生在它们抽到不同集合的时候，所以变回去以后，每条边两端不同的机会，不超过新问题里两端抽到不同集合的机会。

满足两条规矩的这种切层，在论文里叫保持全变差的提升；变回去的那一步，叫共享随机映回。

只看切过层的输入就够了

找最坏的情况时，只看切过层的输入就够了。

用出题游戏来说。出题人随便出一组表，安排人可以先把它切层，在切过层的那组表上安排好，再照上面的办法变回去。距离没有变，两端不同的机会只会减少，所以每一步的倍数都不会变大，原来那组表不会比切过层的那组更难。切过层的表本身也是一组表，出题人本来就可以直接出它。所以出题人想逼出最高分，只出切过层的表就行了。

多走一步：切层以后可能更难，为什么没关系

切层以后的新问题，可能比原问题难一点：原问题能做到的某个倍数，新问题未必做得到。因为切层把一种回答拆成了好几层，原问题里有些灵活的配合方式可能用不上了。

这并不妨碍我们找最坏的情况，理由有两条：

新问题上做得到的倍数，原问题一定也做得到，因为新问题的安排总能变回去，而且不会更差。所以，原问题不会比它切层以后的新问题更难。
新问题本身，也是一组合法的输入：它的“回答”是集合，机会是权重，同样是一组概率表。所以它也在“所有可能的输入”里面。

两条合起来，最坏的情况一定能在“切过层的输入”里找到。

停下来算一算

换一组数：三个顶点回答 $1$ 的机会分别是 $\frac{1}{2}$ 、 $\frac{1}{4}$ 、 $\frac{1}{2}$ 。

回答 $1$ 和回答 $0$ 各切出哪几层？把同名的层合起来，每个集合的权重是多少？
检查每个顶点的权重加起来是不是 $1$ 。
顶点 $1$ 和顶点 $3$ 的表一模一样，距离是 $0$ 。切层以后，它们的距离还是 $0$ 吗？

答案见附录二。

展开本章“停下来算一算”的答案

回答 $1$ 的柱高是 $\frac{1}{2}$ 、 $\frac{1}{4}$ 、 $\frac{1}{2}$ ：最底下 $\frac{1}{4}$ 属于 ${1, 2, 3}$ ，再往上 $\frac{1}{4}$ 属于 ${1, 3}$ 。回答 $0$ 的柱高是 $\frac{1}{2}$ 、 $\frac{3}{4}$ 、 $\frac{1}{2}$ ：最底下 $\frac{1}{2}$ 属于 ${1, 2, 3}$ ，再往上 $\frac{1}{4}$ 属于 ${2}$ 。合起来， ${1, 2, 3}$ 是 $\frac{1}{4} + \frac{1}{2} = \frac{3}{4}$ ， ${1, 3}$ 是 $\frac{1}{4}$ ， ${2}$ 是 $\frac{1}{4}$ 。
顶点 $1$ ： $\frac{3}{4} + \frac{1}{4} = 1$ ；顶点 $2$ ： $\frac{3}{4} + \frac{1}{4} = 1$ ；顶点 $3$ ： $\frac{3}{4} + \frac{1}{4} = 1$ 。
是。顶点 $1$ 和 $3$ 拥有的集合完全一样，都是 ${1, 2, 3}$ 和 ${1, 3}$ ，没有任何差别。顺便可以验证，顶点 $1$ 和 $2$ 原来的距离是 $\frac{1}{4}$ ，切层以后差在 ${1, 3}$ 和 ${2}$ 上， $(\frac{1}{4} + \frac{1}{4}) \div 2$ ，还是 $\frac{1}{4}$ 。

到这一步，回答的种类从“任意多”变成了“最多 $2^{n} - 1$ 种集合”。可是权重仍然可以是任何数，清单还没有变成有限的。