公共币与私有币协议

两种随机资源 ​

公共币协议在看到输入前抽取随机串 $R$，Alice 与 Bob 都能读取它。给定 $R=r$ 后，协议成为一棵确定性通信树。公共随机串独立于 $(x,y)$，不计入消息长度；它协调双方选择同一个哈希函数、采样位置或协议分支，却不能携带当前输入的信息。

私有币协议则让 Alice 持有 $R_A$、Bob 持有 $R_B$，两条随机带彼此独立公理库独立性Statistical independence若干 σ-代数的任意有限事件选择都按概率乘积分解的性质。并对另一方隐藏。任何想让双方共同使用的随机选择都必须通过实际消息协调。私有币不是“双方共享猜测”：Alice 不知道 $R_B$，Bob 也不知道 $R_A$。

记逐输入错误至多 $\epsilon$、最坏通信硬上限下的复杂度为

$$R_{\epsilon }^{\mathrm{pub}}(f),R_{\epsilon }^{\mathrm{priv}}(f).$$

私有币协议可以忽略各自随机带，公共币协议也可以把一方生成的随机性视为自己的公共选择，因此在标准模型中

$$R_{\epsilon }^{\mathrm{pub}}(f)\le R_{\epsilon }^{\mathrm{priv}}(f).$$

这条不等式只比较通信，不表示公共随机性在实现中没有生成或同步成本。

Equality 的 coin 账目 ​

在Equality公理库Equality 通信问题Equality communication problem · EQ communication problem比较双方 n-bit 私有串是否完全相同，展示确定性完整传输与公共随机指纹之间的指数差异。内积指纹中，公共随机向量 $r$ 使双方计算同一个 parity。Alice 只发送指纹 bit，Bob 比较自己的指纹；$k$ 次独立公共选择把错误降为 $2^{-k}$。

若 Alice 用私有币抽 $r$，Bob 无法仅从一个 parity bit 知道她采用哪个线性函数。发送整个 $n$-bit 向量会抹掉通信优势；发送一个来自预先约定小族的种子则可能保留优势，但种子长度必须进入通信。区别不在哈希公式，而在双方如何获得同一个随机函数。

固定一个公共随机串并永久写入协议，也不能给出逐输入正确的短确定性方案。对每个固定压缩映射总有碰撞输入；公共币保证的是每个固定输入只在少量随机串上碰撞，而不是存在一条随机串同时避开所有输入。

Newman 型随机性压缩 ​

设双方输入总长度至多 $N$ bit，一条公共币协议通信至多 $c$，且每个输入错误至多 $\epsilon$。对额外参数 $\delta >0$，Newman 思想给出

$$R_{\epsilon +\delta }^{\mathrm{priv}}(f)\le R_{\epsilon }^{\mathrm{pub}}(f)+O(\log N+\log \frac{1}{\delta }).$$

结论允许错误从 $\epsilon$ 增至 $\epsilon +\delta$。它不是说公共币和私有币逐协议完全等价，而是在有限输入全集、允许小误差松弛时，公共随机性只节省对数级通信。

压缩证明链 ​

对每个固定输入 $u=(x,y)$，令 $E_u(r)\in \{0,1\}$ 表示公共串 $r$ 是否导致错误，且 ${\mathbb{E}}_R{E}_u(R)\le \epsilon$。独立抽取 $t$ 条公共串 $R_1,\dots ,R_t$。Hoeffding 界说明

$$\text{Pr}[\frac{1}{t}\sum _{j=1}^t{E}_u(R_j)>\epsilon +\delta ]\le e^{-2t{\delta }^2}.$$

合法输入对至多 $2^N$ 个。取 $t=O(N/{\delta }^2)$，对全部输入求并后失败概率小于 $1$；因此存在一个固定多重集 $\{r_1,\dots ,r_t\}$，使每个输入在其中至多 $\epsilon +\delta$ 比例的随机串上出错。

把这个多重集公开写入协议。Alice 用私有币均匀选择 $J\in [t]$，发送 $J$ 的编号；双方随后按原公共币协议使用固定串 $r_J$。编号长度

$$\lceil {\log }_{2}t\rceil =O(\log N+\log \frac{1}{\delta }),$$

且每个输入的错误率由构造控制在 $\epsilon +\delta$。这完成从公共币到私有币的模拟；新消息不是“免费公共随机串”，而是把小随机样本族中的索引实际传给 Bob。

适用边界 ​

证明对有限输入全集求并，因而输入长度界 $N$ 必须明确。若输入来自无限精度实数、协议族没有有限离散化，不能把 $2^N$ 的计数凭空代入。通信上限、错误量词和随机串独立性也都要固定。

$R$ 若在看到输入后由某个中央实体选择，就可能把输入编码进“公共随机性”，那已是额外通信或建议字符串。伪随机种子在工程上能否替代真公共币，则依赖对手能力和生成器假设，不是信息论模型自动保证。

随机性压缩控制平均于所选小族的错误，不保证每条 $r_j$ 都对所有输入正确。模拟后仍是随机协议；把 Alice 发送的索引固定为某个常数，会再次落入确定性碰撞障碍。

参考资料

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