随机通信复杂度 | Codeboy's Blog

形式陈述

随机性放在协议哪里

在两方通信模型上加入随机币，得到随机协议 $\Pi(x,y;R_A,R_B)$ ，其中 $R_A,R_B$ 是双方的私有随机币。它与确定性协议是同一基础模型上的平行变体，不以“确定性通信复杂度”这个度量为构造前置。给定 $(x,y)$ 与两条随机带后，协议变成确定性消息过程，产生 transcript、输出和通信量。随机性不会改变输入，也不会让一方直接看见另一方的私有币。

本页以私有币、双侧误差和最坏通信硬上限为基线。协议以误差 $\varepsilon$ 计算 $f$ ，若对每个固定输入对都有

\Pr_{R_A,R_B} \bigl[\Pi(x,y;R_A,R_B)\ne f(x,y)\bigr] \le\varepsilon.

在每次随机选择都发送至多 $c$ bit 的协议中取最小 $c$ ，得到 $R^{\mathrm{cc,priv}}_\varepsilon(f)$ 。通常在上下文已经固定 coin model 后简写为 $R^{\mathrm{cc}}_\varepsilon(f)$ ；若同时讨论查询复杂度，保留上标可避免与其 $R_\varepsilon(f)$ 混淆。

随机化算法的基本量词在这里仍然有效：先固定输入，再对内部随机性取概率。把输入也按某个分布抽样并只控制平均错误，会得到另一个分布模型，不能替代上述逐输入保证。

通信成本有两种常用口径

硬上限口径要求

\max_{x,y,r_A,r_B} c_\Pi(x,y;r_A,r_B)\le c.

期望通信口径则可能要求 $\max_{x,y}\mathbb E_R[c_\Pi(x,y;R)]\le c$ 。后者允许极少数随机带产生很长 transcript，前者不允许。即使二者最后都写成 $O(g(n))$ ，保证仍不相同。

还有一个容易误换的式子：

\max_{x,y}\mathbb E_R[c_\Pi(x,y;R)] \quad\text{与}\quad \mathbb E_R\!\left[\max_{x,y}c_\Pi(x,y;R)\right].

第一式允许每条随机带的坏输入不同，第二式则对每次固定随机选择都寻找最坏输入，通常更强。比较文献结论时，必须先对齐通信成本和错误概率各自的量词。

直觉

随机协议不是一棵偶尔走错的确定性树，而是一族确定性树的分布。对某个输入表现不好的树可以存在，只要它在随机选择中所占比例受控；不同输入甚至可以由不同树负责出错。随机化的力量正来自允许这些坏集合错开，而不是找到一棵同时照顾全部输入的短树。

固定输入后，随机种子选择一条确定性协议，其中错误协议所占概率至多 epsilon — 随机协议是确定性协议的分布

通信量与错误率又各有自己的最坏对象。硬上限要求每条随机轨迹都不超预算，期望口径允许少数长对话；逐输入错误先固定 $(x,y)$ ，分布错误则还对输入取平均。只有把这些量词按原顺序写清，才能判断一次固定随机币、截断或放大是否仍在同一个模型中。

例子与边界

随机通信复杂度要求一个随机协议对每个输入都控制错误；分布通信复杂度固定输入分布，只要求确定性协议在该分布下平均错误小。Yao 原理连接两者的极小极大值，但单个分布保证不等于逐输入保证。

一个带 gap 的随机协议

考虑 promise 问题：Alice 与 Bob 各持 $n$ bit 串，合法输入要么满足 $x=y$ ，要么满足 $d_H(x,y)\ge n/3$ ；目标区分这两种情形。Alice 私下均匀抽取坐标 $I\in\{1,\ldots,n\}$ ，向 Bob 发送 $I$ 的编码和 bit $x_I$ 。Bob 比较它与 $y_I$ ，不同就拒绝，相同则暂时接受。

当 $x=y$ 时，任何随机坐标都一致，协议从不误拒。若两串至少三分之一坐标不同，一次抽样漏掉差异的概率至多 $2/3$ 。独立重复 $k$ 次，并且只有全部坐标都相同才接受，坏输入的误收概率至多

\left(\frac23\right)^k.

通信量为 $k(\lceil\log_2n\rceil+1)$ bit。每轮中 Alice 发送抽到的索引，所以协议没有假装双方免费共享她的私有随机选择；Bob 无需随机币也能验证收到的位置。

这个例子的 promise 是保证的核心，而不是装饰。去掉 $n/3$ 的距离下界后，两串可能只差一个坐标，一次抽样发现差异的概率仅为 $1/n$ ；固定常数次重复几乎总会漏掉。把 gap 例子的错误界直接写成普通 Equality 协议，会把一个错误算法包装成随机化优势。

固定随机币与协议树

固定 $(r_A,r_B)$ 后，随机协议确实成为一棵确定性协议树。但这棵树不必在所有输入上正确。逐输入误差界只说明：对每个 $(x,y)$ ，使该输入走向错误叶的随机币集合概率至多 $\varepsilon$ 。

量词交换是无效推理的常见来源。由“每个输入各有至少 $1-\varepsilon$ 比例的好随机币”，不能推出“存在同一条随机带，对全部输入同时正确”。输入数巨大时，各输入的坏随机币集合可以覆盖整个随机空间。若真找到一条对所有输入都正确的固定随机带，那会给出确定性协议，是远强于 bounded-error 定义的结论。

公共随机币允许双方在通信前看见同一随机串；私有随机币则分别隐藏。两种模型及其转换需要单独记录共享性和额外消息，本页不把它们压成“都有随机数”的同一协议。无论哪种模型，公共串本身不计通信并不意味着它携带输入信息：它必须在看到 $x,y$ 之前独立产生。

错误类型与放大边界

双侧误差允许两类输入都以小概率答错；单侧误差要求其中一类永不出错；零误差协议则每次输出都正确，但运行时间或通信量可以成为随机变量。多数表决适合具有固定成功偏差的双侧错误，单侧协议常用 OR 或 AND 聚合保留永不出错的一侧。聚合规则必须与错误结构匹配。

概率放大还要求各次试验拥有足够独立的随机性。机械重复同一随机种子不会把错误概率从 $\varepsilon$ 变成 $\varepsilon^k$ ，它只把同一错误决定复制 $k$ 次。重复也按比例增加通信；不能只更新成功概率而保留原消息长度。

最后，随机通信上界仍在免费本地计算模型中。用一个信息论上存在但难以求值的随机编码，不能自动得到高效分布式算法；而在这种强模型中成立的通信下界，才可作为其他受限模型的稳健障碍。

推论与应用

固定随机币把随机协议接回确定性协议树，是分布下界的标准入口：先选一份对所有协议共同的困难输入分布，再从平均错误低的随机协议中固定出一棵分布错误低的树，最后对这棵树使用矩形或信息论证。困难分布若随树改变，量词链就已断裂。

在上界侧，独立重复能把常数偏差放大，但会成比例增加通信，并必须按单侧、双侧或零误差选择聚合规则。公共币、私有币、期望成本和最坏成本之间的转换都可能再付消息或错误松弛，不能用一个未加标记的 $R(f)$ 掩盖。

参考资料

Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 3.
Ilan Newman, “Private vs. Common Random Bits in Communication Complexity,” Information Processing Letters 39(2), 1991, pp. 67–71.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 3–4.

形式陈述 ​

随机性放在协议哪里 ​

通信成本有两种常用口径 ​

一个带 gap 的随机协议 ​

固定随机币与协议树 ​