附录三给想多走一步的读者

这一部分把正文里借用的几个结论补上理由。有些地方用到了高中或大学的数学，跳过它们不影响理解正文。

一、最大耦合

对两张表 $p$、$q$，两栏都写回答 $a$ 的机会，不可能超过 $p(a)$，也不可能超过 $q(a)$，所以不超过两者中较小的那个。把所有回答加起来，两栏相同的机会不超过 ${\sum }_a\min \{p(a),q(a)\}$，不同的机会至少是 $$1-\sum _a\min \{p(a),q(a)\}$$ 这个数等于全变差距离。因为对每种回答都有 $$|p(a)-q(a)|=p(a)+q(a)-2\min \{p(a),q(a)\}$$ 全部加起来再除以 $2$，就是 $1-{\sum }_a\min \{p(a),q(a)\}$。

要做到这个下限，就先把每种回答上较小的那部分配成“两栏相同”，再把两边各自剩下的部分任意配对。剩下的部分，在 $p$ 这边和 $q$ 这边总量相等，都等于全变差距离；而且它们落在不同的回答上，配对后两栏一定不同。第六章的例子就是这样填出来的。

二、树上的拼接

在树上，从根开始依次抽。设父顶点 $u$ 已经抽好，它的边际分布是 ${\mu }_u$，边 $uv$ 选定的联合分布是 $M$（它的两个边际分别是 ${\mu }_u$ 和 ${\mu }_v$）。在 $u$ 回答 $a$ 的条件下，让 $v$ 回答 $b$ 的机会是 $\frac{M(a,b)}{{\mu }_u(a)}$。那么“$u$ 回答 $a$、$v$ 回答 $b$”的机会是 ${\mu }_u(a)\cdot \frac{M(a,b)}{{\mu }_u(a)}=M(a,b)$，正好是选定的联合分布。${\mu }_u(a)=0$ 的回答根本不会出现，那里的条件规则怎样补都不影响结果。树上每个新顶点只有一个已抽好的邻居，所以这样一路抽下去，每条边的联合分布都是选定的那一个。

三、平衡删边

记号沿用第十一章：$d_e$ 是边 $e$ 两端的全变差距离，$D$ 是圈上各边距离之和，$p_e$ 是边 $e$ 被拿掉的机会，$S={\sum }_e\frac{d_e}{D-2d_e}$。

为什么是最好的选法。 设各边都满足 $0<d_e<\frac{D}{2}$，记 $a_e=\frac{D-2d_e}{d_e}$。随机拿掉边的办法给出的倍数上界是各边 $1+a_e{p}_e$ 中最大的那个，记作 $t$。那么每条边都满足 $p_e\le \frac{t-1}{a_e}$。把这些不等式加起来，左边是 ${\sum }_e{p}_e=1$，所以 $$1\le (t-1)\sum _e\frac{1}{a_e}=(t-1)S$$ 也就是 $t\ge 1+\frac{1}{S}$。祺乐的平衡式正好让每个不等式都取等号，达到这个下限；而且要让总和取等号，每一条都必须取等号，所以最好的选法只有这一种。

为什么不超过 $2-\frac{2}{m}$。 设距离为正的边有 $m$ 条，令 $x_e=\frac{d_e}{D}$，它们都在 $0$ 和 $\frac{1}{2}$ 之间，加起来等于 $1$。注意 $$\frac{x}{1-2x}=\frac{1}{2}(\frac{1}{1-2x}-1)$$ 记 $y_e=1-2x_e$，它们都是正数，加起来等于 $m-2$。于是 $$S=\frac{1}{2}(\sum _e\frac{1}{y_e}-m)$$

先证明一个初中就能证的不等式：对任意 $m$ 个正数 $y_1,\dots ,y_m$， $$(y_1+\cdots +y_m)(\frac{1}{y_1}+\cdots +\frac{1}{y_m})\ge m^2$$ 把左边乘开，得到 $m$ 个 $1$，以及每一对 $i<j$ 贡献的 $\frac{y_i}{y_j}+\frac{y_j}{y_i}$。由 $(y_i-y_j{)}^2\ge 0$ 可得 $\frac{y_i}{y_j}+\frac{y_j}{y_i}\ge 2$，而这样的对一共有 $\frac{m(m-1)}{2}$ 对，所以左边至少是 $m+m(m-1)=m^2$。

用在这里：${\sum }_e\frac{1}{y_e}\ge \frac{m^2}{m-2}$，所以 $$S\ge \frac{1}{2}(\frac{m^2}{m-2}-m)=\frac{m}{m-2},1+\frac{1}{S}\le 1+\frac{m-2}{m}=2-\frac{2}{m}$$ 各条边距离相等时等号成立。

四、切层的两个等式

固定一种回答 $a$，把各顶点的 ${\mu }_v(a)$ 从小到大排好。用一条水平线从下往上扫，扫到高度 $h$ 时，“柱子高度不低于 $h$”的顶点构成一个集合。高度在相邻两个柱顶之间时，这个集合不变；越过一个柱顶，集合就少掉一个顶点。所以一根柱子从 $0$ 到它的顶，恰好被那些“包含它的层”不重不漏地分完： $${\mu }_v(a)=\sum _{S\ni v}{h}_S(a)$$ 两根柱子 $u$、$v$ 的高度差，恰好是那些只包含其中一个的层的厚度之和： $$|{\mu }_u(a)-{\mu }_v(a)|=\sum _S{h}_S(a)|1_{u\in S}-1_{v\in S}|$$ 这里 $1_{u\in S}$ 在 $u$ 属于 $S$ 时等于 $1$，否则等于 $0$。第一个等式对所有回答加起来，说明每个顶点包含它的权重之和是 $1$；第二个等式对所有回答加起来再除以 $2$，说明全变差距离不变。有几根柱子一样高时，等式仍然成立，只是有些层的厚度是零。

五、为什么一个角最多用 $n$ 个集合

把每个集合 $S$ 写成一列 $n$ 个数：第 $v$ 个位置上，$v$ 在 $S$ 里就写 $1$，否则写 $0$。覆盖条件就是：这些列按权重加起来，等于每个位置都是 $1$ 的那一列。

如果一个角上，权重为正的那些集合对应的列之间线性相关，也就是存在一组不全为零的数 $z_S$，让每一列乘上对应的 $z_S$ 再加起来，得到全是零的一列，那么把权重改成 ${\lambda }_S\pm t{z}_S$，覆盖条件仍然成立；$t$ 足够小时，所有权重仍然不是负数。原来的点就是这两个合法点的中点，不是角。所以在角上，这些列必须线性无关。

每列只有 $n$ 个数，线性无关的列最多 $n$ 列（这是线性代数里的基本事实：$n$ 个方程、超过 $n$ 个未知数的齐次方程组一定有不全为零的解）。所以一个角上权重为正的集合最多 $n$ 个。反过来也成立：如果一组合法权重的正权重集合对应的列线性无关，它就是一个角。

六、分数与行列式

在一个角上，挑出权重为正的 $r$ 个集合，它们的列线性无关，所以可以从 $n$ 行里挑出 $r$ 行，组成一个 $r$ 行 $r$ 列、行列式不为零的 $0/1$ 方阵 $B$，满足“$B$ 乘以这些权重等于全 $1$”。按克拉默法则（第十九章二元方程组公式的推广），每个权重都等于两个整数行列式之比，分母都是 $\det B$。所以每个权重都是 $\frac{1}{|\det B|}$ 的整数倍。

为了估计 $|\det B|$ 最大能有多大，论文用了下面的办法。设 $F$ 是全是 $1$ 的 $r$ 阶方阵，作一个 $r+1$ 阶方阵 $$H=\left(\begin{array}{cc}1& 1\cdots 1\\ \begin{array}{c}1\\ ⋮\\ 1\end{array}& F-2B\end{array}\right)$$ 它的每个元素都是 $1$ 或 $-1$。把第一行从其余各行中减去，可以算出 $|\det H|=2^r|\det B|$。另一方面，有一个叫阿达马不等式的结论：行列式的绝对值不超过各行长度的乘积。$H$ 的每一行有 $r+1$ 个 $\pm 1$，长度是 $\sqrt{r+1}$，所以 $|\det H|\le (r+1{)}^{(r+1)/2}$。合起来： $$|\det B|\le \frac{(r+1{)}^{(r+1)/2}}{2^r}$$ $r=2$ 时右边约是 $1.30$，$r=3$ 时是 $2$，$r=4$ 时约是 $3.49$。行列式是整数，所以分别不超过 $1$、$2$、$3$。这就是第十九章用到的 ${\Delta }_2\le 1$、${\Delta }_3\le 2$、${\Delta }_4\le 3$。

七、计时器赛跑

这一节要用到指数分布，是高中以后的内容。

给每种回答 $a$ 配一个独立的随机数 $E_a$，它服从“速率为 $1$ 的指数分布”：$E_a$ 大于 $t$ 的机会是 $e^{-t}$。表为 $p$ 的顶点，把回答 $a$ 的计时器定为 $\frac{E_a}{p(a)}$（$p(a)=0$ 的回答不参加），输出最先响的那个。

边际分布正确。 $\frac{E_a}{p(a)}$ 是一个速率为 $p(a)$ 的指数随机数。几个独立的指数计时器里，某一个最先响的机会，等于它的速率占总速率的比例。总速率是 ${\sum }_{a}p(a)=1$，所以输出 $a$ 的机会正好是 $p(a)$。

不同的机会不超过 $\frac{2d}{1+d}$。 对两张表 $p$、$q$，设 $p(a)$、$q(a)$ 都大于零。两边都输出 $a$，要求对每个别的回答 $b$，两边的 $b$ 计时器都比 $a$ 晚响。按 $E_a$ 的取值积分，可以算出这件事的机会是 $$\frac{1}{{\sum }_b\max \{\frac{p(b)}{p(a)},\frac{q(b)}{q(a)}\}}$$ 分母里的每一项都不超过 $$\frac{\max \{p(b),q(b)\}}{\min \{p(a),q(a)\}}$$ 而 ${\sum }_b\max \{p(b),q(b)\}=1+d$，其中 $d$ 是全变差距离。所以两边都输出 $a$ 的机会至少是 $$\frac{\min \{p(a),q(a)\}}{1+d}$$ 对所有 $a$ 加起来，两边相同的机会至少是 $\frac{1-d}{1+d}$，不同的机会至多是 $\frac{2d}{1+d}$。

八、超立方体的边连通度

要证明：把 $Q_d$ 分成两块，至少要剪断 $d$ 条边。$d=1$ 时显然。把 $Q_d$ 看成两个 $Q_{d-1}$，对应的顶点再一一连起来。对一种把顶点分成两边的切法：

• 如果两个 $Q_{d-1}$ 都被切开了，按归纳假设各自至少贡献 $d-1$ 条被剪断的边，共 $2(d-1)\ge d$ 条（$d\ge 2$）；
• 如果只有一个被切开，它内部至少贡献 $d-1$ 条；另一个整个在同一边，被切开的那一个里，总有顶点在另一边，它和对面副本的连线也被剪断，所以至少再多一条；
• 如果两个都没被切开，切法只能是把两个副本分开，被剪断的是全部 $2^{d-1}$ 条连线，而 $2^{d-1}\ge d$。

所以至少要剪 $d$ 条。把一个顶点单独切下来，正好剪 $d$ 条，所以边连通度恰好是 $d$。

九、对偶证书为什么给出下限

线性规划里，对每条边 $e=uv$，记两端两张表的全变差距离为 $d_e$、两栏不同的机会为 $q_e$，有限制 $q_e\le c\cdot d_e$。对偶证书给出一些数：$y_0$、每个“顶点—回答”对应的 $y_{v,a}$（可正可负），以及每条边的 $z_e\le 0$，要求：

• 对每一种完整的签 $x$：$y_0+{\sum }_v{y}_{v,x_v}+{\sum }_{e=uv}{z}_e\cdot [x_u\ne x_v]\le 0$，其中 $[x_u\ne x_v]$ 在两栏不同时是 $1$，否则是 $0$；
• $-{\sum }_e{z}_e{d}_e\le 1$。

把第一条不等式按每种签的机会加权加起来：$y_0$ 乘以总机会 $1$；${\sum }_v{y}_{v,x_v}$ 加起来变成 ${\sum }_{v,a}{y}_{v,a}{\mu }_v(a)$；最后一项变成 ${\sum }_e{z}_e{q}_e$。于是 $$y_0+\sum _{v,a}{y}_{v,a}{\mu }_v(a)\le -\sum _e{z}_e{q}_e\le -\sum _e{z}_{e}c{d}_e\le c$$ 第二个不等号用了 $z_e\le 0$ 和 $q_e\le c{d}_e$，最后一个用了 $-{\sum }_e{z}_e{d}_e\le 1$。左边只由给定的表和证书决定，所以它是所有可行的 $c$ 的下限。第八章的计数论证，就是这样一份证书的特例。

十、需要多少计算

第十四章讲了在仙人掌图上怎样真的抽一次签，这里估计一下它要花多少计算。如果所有顶点的表都事先给定，准备工作的计算量和存储量，大致和“（顶点数 ＋ 边数）× 回答种数”成正比。准备好以后，抽一次完整的签就很快：每个顶点只要定位自己抽中的是哪种回答。这里可以用一种叫二分查找的技巧，像猜数字游戏那样，每次把范围砍掉一半。回答有一千种的话，大约十步就能定位。

这些估计把一次加减乘除算作一步。如果要用分数做精确计算，分母很大的时候，每一步本身也会变慢；生成随机数需要多少随机比特，也没有算在里面。论文附带的一些程序，为了生成可以逐项检查的证据，会把完整的联合分布全部列出来，它们的计算量和这里的快速抽法不是一回事。