信息复杂度

形式陈述 ​

随机变量与 transcript ​

固定输入分布 $\mu$，令 $(X,Y)\sim \mu$。随机协议公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。使用公共币 $R$ 和双方私有币，消息 transcript 记为 $T$。本页把 $R$ 与消息分开写，并假设 $R$ 独立于 $(X,Y)$；条件在 $R$ 上可以避免把免费共享随机串误计为输入泄露。

协议的 internal information cost 定义为

$${\mathrm{IC}}_{\mu }^{\mathrm{int}}(\mathrm{\Pi })=I(X;T\mid Y,R)+I(Y;T\mid X,R).$$

第一项量化 Bob 已知 $Y,R$ 后从对话新学到多少关于 $X$ 的信息；第二项对称地量化 Alice 的新增知识。互信息公理库互信息Mutual information一个随机变量对另一个随机变量不确定性的平均减少量。按 bit 计时使用底为 $2$ 的对数。

External information cost 定义为

$${\mathrm{IC}}_{\mu }^{\mathrm{ext}}(\mathrm{\Pi })=I(X,Y;T\mid R),$$

它站在只知道公共币的外部观察者角度，问消息整体泄露多少关于输入对的信息。Internal 与 external 回答不同接收者的知识增量，不能只写“transcript 含有多少信息”而省略条件变量。

条件熵展开 ​

由条件熵公理库条件熵Conditional entropy已知一个随机变量后另一个随机变量剩余不确定性的平均值。恒等式，

$$I(X;T\mid Y,R)=H(X\mid Y,R)-H(X\mid T,Y,R).$$

因此 internal 第一项是 Bob 的不确定性下降；如果 $Y$ 已经完全决定 $X$，Alice 即使发送 $X$，这项仍为 $0$。External 观察者没有 $Y$，同一消息却可能泄露很多。

两种成本的差满足

$${\mathrm{IC}}_{\mu }^{\mathrm{int}}(\mathrm{\Pi })-{\mathrm{IC}}_{\mu }^{\mathrm{ext}}(\mathrm{\Pi })=I(X;Y\mid T,R)-I(X;Y\mid R).$$

transcript 可以增加或减少条件相关性，所以 internal 与 external 没有在任意相关输入分布下的固定大小顺序。若 $X,Y$ 独立，右侧非负，internal 至少 external；相关输入时结论可能改变。

信息成本不超过通信 ​

对 prefix-free 的变长 transcript，有

$${\mathrm{IC}}_{\mu }^{\mathrm{int}}(\mathrm{\Pi })\le \mathbb{E}[|T|],{\mathrm{IC}}_{\mu }^{\mathrm{ext}}(\mathrm{\Pi })\le \mathbb{E}[|T|].$$

External 不等式来自 $I(X,Y;T\mid R)\le H(T\mid R)$，而 prefix-free 编码的期望长度至少为 transcript 熵。Internal 不等式可按消息链展开：Alice 发出的每个 bit 对 $I(X;T\mid Y,R)$ 的新增贡献至多一 bit，Bob 消息对另一项同理；把各轮贡献求和不超过发送长度。

函数的信息复杂度 ​

在分布 $\mu$ 下，以平均错误至多 $\epsilon$ 计算函数 $f$ 的协议中取 information cost 下确界，定义

$${\mathrm{IC}}_{\mu ,\epsilon }^{\mathrm{int}}(f)=\underset{\mathrm{\Pi }:{\mathrm{err}}_{\mu }(\mathrm{\Pi },f)\le \epsilon }{inf}{\mathrm{IC}}_{\mu }^{\mathrm{int}}(\mathrm{\Pi }),$$

external 版本同理。协议可有不同通信量；定义优化的是输入泄露，不是 transcript 长度。若要 worst-case error，应把合法协议集合改成逐输入错误约束，不能默认由平均错误替代。

直觉

通信量记录线路上实际经过多少 bit，信息成本则记录这些 bit 让接收者的输入不确定性下降了多少。已经由自己的输入推知的内容、与输入无关的 padding 或机械重复都会占用带宽，却未必带来新的互信息；反过来，多轮协议的每条短消息都可能依据先前 transcript 精细调整，信息成本可以逐轮追踪这种知识转移。

Internal 与 external 的区别在于“谁在观察”。双方各自带着一份私有输入，某条消息对他们可能毫无新意；外部观察者没有这些侧信息，却可能从同一 transcript 学到完整事实。条件变量不是公式装饰，而是在准确描述观察者通信前已经知道什么。

例子与边界

一 bit 消息的两种视角 ​

令 $X$ 为均匀 bit，并令 $Y=X$。Alice 发送 $T=X$。通信量为一 bit，external cost 为

$$I(X,Y;T)=H(X)=1,$$

因为外部观察者从消息学会共同输入。Internal cost 却为

$$I(X;T\mid Y)+I(Y;T\mid X)=0+0=0,$$

双方在通信前已经由自己的输入知道对方输入。这个例子说明“消息长度一 bit”不等于“双方之间传递一 bit 新信息”。

反过来，Alice 发送一个与输入独立的均匀随机 padding bit，通信仍为一 bit，internal 和 external information cost 都为 $0$。信息成本会忽略无关冗余，而通信成本必须为每个实际发送 bit 付费。

边界与 convention ​

公共币若直接并入 transcript，因其与输入独立，external 互信息不变；internal 公式仍应对它条件化。私有币不应无条件放进外部 transcript，因为对方没有看到它们；只有由消息暴露的部分才构成通信信息。

消息边界若不是 prefix-free，结束时间可能携带信息，$H(T)\le \mathbb{E}|T|$ 的直接编码论解释需加入终止符。通信模型通常用协议树叶保证自定界。

最后，information cost 是关于给定 $\mu$ 的量。改变输入相关性会改变先验条件熵，甚至让同一协议 internal cost 从正值降为零；报告数值时不能遗漏分布。

推论与应用

信息成本不超过期望通信，因此任何 information-cost 下界都会推出通信下界；反向等号不必成立，随机 padding、重复消息和双方已知的相关信息都能制造差距。使用这条桥梁时仍要对齐同一输入分布、错误口径与 transcript 编码，否则下界约束的不是原协议集合。

它尤其适合分析多轮问题的 direct-sum、压缩与摊销现象，因为互信息能按消息链式分解，也能区分不同输入副本贡献。但具体函数下界仍需证明每个正确协议都泄露足够信息；只把协议写成互信息公式，并不会自动产生正下界。

参考资料

• Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar, “An Information Statistics Approach to Data Stream and Communication Complexity,” FOCS, 2002, pp. 209–218.
• Mark Braverman, “Interactive Information Complexity,” STOC, 2012, pp. 505–524.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 5–6.