第二十三章只看自己那张表

后来写进论文的“只看自己的表”，起头是韵吉和祺乐一起去问 AI 的一个问题：如果每个顶点只能看到自己的分布，不知道别的顶点的分布，倍数还能做到小于 $2$ 吗？

AI 的回答很干脆：恰好是 $2$，做不到小于 $2$。下界用的是逐一缺失的表，让回答的种类越来越多；上界用的是前人的一种抽签办法。

韵吉在“恰好是 $2$”下面画了一道线，又翻回第六章：“一条边的时候，不是能做到 $1$ 吗？”

各自开工的助手

到目前为止，我们一直默认：写答案单的人，可以先看到所有情况的签盒，再决定怎样切层、怎样混合、怎样变回去。这叫集中式的安排。

现在换一种助手。每种保留情况下的助手各自开工，手里只有自己这一种情况的签盒，外加一样大家共用的东西，比如一组闹钟，或者绳子上点好的一个位置。怎样用这些东西抽签，要事先写成一本手册，以后不管遇到什么签盒，都照手册办。要是真实的系统删掉一条记录以后，只拿这一种情况下的分布重新回答，它就属于这一种。

去掉名字来说：每个顶点只能看到自己那张表，再加上一个大家共用的随机源。

先交手册，还是先看题

用第九章的出题游戏来说，规则只改了一条：安排人必须先交手册，再看题。手册里写的是，每种情况拿到自己的签盒以后，怎样拨那组共用的闹钟。出题人先说好这一场有哪些去处，种类可以要多少有多少；安排人照着这些去处写好手册交上去，出题人才定每个签盒里的机会。

这件事要说清楚并不容易，我们在这里卡了很久。论文致谢里写的几个主要困难之一，就是“分布访问条件的量词”。这里的“量词”，指“对每一个”“存在一个”这样的词。说白了，就是要说清楚谁在什么时候能看到什么，什么先定、什么后定。

韵吉在一张纸上写了两句话，字几乎一样，只是前后对调：

对每一组签盒，都有一种安排……

有一种手册，对每一组签盒……

“差在哪儿？”韵吉问。

祺乐看了好一会儿：“第二句像是考试前先把答案交上去。”

第一句是第六章的做法：先看到两张具体的表，再专门为它们设计最好的两栏签，一条边当然能做到 $1$。第二句是现在的处境：先交出一本固定的手册，以后不管出题人给哪一对签盒，都要靠这同一本手册兑现保证。

严格地说，“只看自己的表”是这样的：回答有哪几种可以先说好，多少种都行；然后事先定好一套规则。每个顶点按这套规则，只根据自己的表和共用的随机源，决定自己的回答。规则一旦定好，就要对所有可能的表都适用，不能看了具体的输入再改。

下界：至少是二

先说明这种情况下，倍数不可能统一地小于 $2$。

手册既然要对什么签盒都管用，出题人就可以发明任意多种回答，四个去处装不下，只能编号。麻烦在于，一套事先定好、只看自己的表的规则，实际上要同时应付所有可能的表。把很多张逐一缺失的表一起交给同一套规则，就像把它们放在一张完全图的各个顶点上，再用第八章“按行算、按列算”的办法数一数，就躲不开了；而表的张数可以任意多，倍数就可以任意接近 $2$。

放到出题游戏里，就是安排人交了手册以后，出题人能把分数逼得要多接近 $2$ 有多接近。下面会看到，安排人只要用对了手册，分数又总在 $2$ 以下。

上界：一组共用的闹钟

$2$ 也做得到。前人给出过一个很巧妙的办法，叫“计时器赛跑”。放进周末的小世界里，计时器就是闹钟。

四个去处各配一个闹钟，所有情况共用这一组闹钟：每个闹钟原本定在什么时候响，是随机定的，大家用的是同一份。每种情况下的助手，按自己签盒里的机会把闹钟拨快：机会越大，拨得越多，平均响得越早；机会是 $0$ 的去处，闹钟干脆关掉，比如怕吵还在时的游乐场。然后看哪个闹钟最先响，就去哪儿。

两种情况的签盒一样时，拨法也一样，回答一定相同，正合第九章“距离为零的边必须一次也不换”的规矩。

去掉名字来说：给每一种回答配一个计时器，所有顶点共用这一组计时器，它们响起的时刻是随机的。每个顶点按自己的表调快计时器，看哪一个最先响，就输出哪种回答。可以证明，用这种方法，每个顶点输出各种回答的机会，正好是它自己那张表；而两个顶点回答不同的机会，不超过它们距离的 $\frac{2}{1+d}$ 倍（$d$ 是两张表的距离），所以一定不超过 $2$ 倍。具体的计算放在附录三。

第十九章借用的那个 $\frac{2d}{1+d}$，用的正是这组计时器。

回到标准签盒。删掉电影约定，就是从“两条都在”走到“只剩怕吵”。两种情况各拨各的闹钟，换地方的机会可以用附录三的式子算准：两边都去电影院的机会是 $\frac{1}{5}$，都去公园是 $\frac{3}{10}$，都去图书馆是 $\frac{6}{31}$，加起来是 $\frac{43}{62}$，所以换地方的机会是 $\frac{19}{62}$，大约 $0.31$。单独安排时最好是 $\frac{3}{10}$，倍数是 $\frac{19}{62}÷\frac{3}{10}=\frac{95}{93}$，大约 $1.02$。这一步，闹钟只比最好的答案单多付了一点点。这几个分数怎样算，写在下面的方框里，只用到分数的加减乘除。

所以，在“只看自己的表、事先定规则、对任意多种回答都适用”的条件下，最好的统一倍数恰好是 $2$，不管图是什么形状，只要图连通而且至少有一条边。

只问去不去电影院

如果只问一件事：周六去不去电影院？回答就只有两种。还记得第四章那根长度为 $1$ 的绳子吗？现在所有情况共用同一根绳子，在上面随便点一个位置，记作 $U$。每种情况在自己去电影院的机会处画一道门槛：$U$ 落在门槛左边就去电影院，否则不去。

用标准签盒。“两条都在”时，去电影院的机会是 $\frac{5}{10}$；“只剩怕吵”时是 $\frac{2}{10}$。两道门槛画在 $\frac{2}{10}$ 和 $\frac{5}{10}$。$U$ 落在 $\frac{2}{10}$ 左边，两种情况都去电影院；落在 $\frac{5}{10}$ 右边，都不去；只有落在两道门槛之间，删约定这一步才会改主意。这一段长 $\frac{3}{10}$，正好是单独安排时最低要换的机会。

去掉名字，回答记作 $0$ 和 $1$。每个顶点只需要知道自己回答 $1$ 的机会，记作 $\theta$（希腊字母，读作“西塔”），在 $\theta$ 处画门槛：$U\le \theta$ 就回答 $1$，否则回答 $0$。两个顶点的回答不同，只发生在 $U$ 落在它们两个门槛之间的时候，这段长度正好是两个 $\theta$ 之差，也就是它们的全变差距离。所以在任何图上，所有边都能同时做到最大耦合，倍数是 $1$。

这和“倍数至少是 $2$”并不矛盾。那个结论要求同一套规则对任意多种回答都适用；只有两种回答，是一个特别容易的小范围。

它也解释了第十一章留下的那个例子。那是随便编的一组数，和周末的记录对不上，所以只用顶点编号。四个顶点排成一个圈，回答 $1$ 的机会依次是 $\frac{1}{10}$、$\frac{4}{10}$、$\frac{2}{10}$、$\frac{5}{10}$。四条边的距离是 $\frac{3}{10}$、$\frac{2}{10}$、$\frac{3}{10}$、$\frac{4}{10}$，加起来 $D=\frac{6}{5}$，平衡式给出 $S=\frac{9}{4}$，倍数上界是 $1+\frac{4}{9}=\frac{13}{9}$。可是用共同门槛，这组表的倍数是 $1$。所以 $\frac{13}{9}$ 只是平衡式这一种构造给出的上界，这组表本身最好能做到 $1$。

集中式和只看自己的表

把两种情况放在一起：

• 能看到所有顶点的表：每一张固定的、连通的、至少有一条边的图，耦合常数严格小于 $2$；
• 只能看到自己的表，而且事先定好的规则要对任意多种回答都适用：最好的倍数恰好是 $2$。

这两个 $2$ 要分清。计时器对每一对具体的表，都做到了小于 $2$ 倍；可是找不到一个比 $2$ 小的数，能对所有的表统一成立。第十九章的“严格小于 $2$”，是先看到全部的表，再为一张固定的图量身安排，所以能做得更好。

回到真实的助手。如果每种保留情况下的助手只知道自己的签盒，再加一组共用的闹钟，删掉一条记录时，回答换地方的机会最多是单独最好时的 $2$ 倍；可也没法统一地做得比 $2$ 倍更好。想更好，就得有一张能看到所有签盒的答案单，也就是前面那种集中式的安排。

记分牌上，$Q_3$ 占了 $\frac{7}{4}$ 到 $2$ 之间的一段，$2$ 这一头标上了“只看自己的表”。