随机通信复杂度

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

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

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

一个带 gap 的随机协议 ​

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

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

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

这里规定 Bob 输出；若要求公开叶输出，还须把最终判定发回。若改用公共币生成同样的坐标，两人都预先知道每次查哪里，Alice 每次只需发送 $x_I$，总通信降为 $k$ bit。改进来自索引已共享，而不是因为随机抽样本身换了一种概率分析。

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

固定随机币与协议树 ​

固定 $(r_A,r_B)$ 后，随机协议确实成为一棵确定性协议树公理库协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。。但这棵树不必在所有输入上正确。逐输入误差界只说明：对每个 $(x,y)$，使该输入走向错误叶的随机币集合概率至多 $\epsilon$。

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

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

错误类型与放大边界 ​

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

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

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

固定随机币把随机协议接回确定性协议树，是分布下界的标准入口：先选一份对所有协议共同的困难输入分布，再从平均错误低的随机协议中固定出一棵分布错误低的树，最后对这棵树使用矩形或信息论证。困难分布若随树改变，量词链就已断裂。硬上限在这一步特别方便：固定任何随机币，树仍不超预算。期望成本没有这个自动保证；例如在通信超过 $c/\eta$ 时截断一个逐输入期望至多 $c$ 的协议，Markov 不等式公理库Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。只保证额外错误至多 $\eta$，成本和误差必须同时更新。

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

通信硬上限还可以与信息复杂度公理库信息复杂度Information complexity · Information cost of a protocol · Internal information cost · External information cost从私有随机带的因子分解证明信息成本界，完整计算 AND 协议的内部、外部、平均与最坏成本，并区分输出熵。逐层比较：对合法的有界深度协议，内部信息不超过外部信息，外部信息不超过分布平均通信，后者才由最坏长度控制。独立公平输入的三叶 AND 协议把这一区别具体化：最坏长度为 $2$，平均长度及两种信息成本均为 $3/2$；随机协议类包含这个不用随机币的特例。