信息复杂度

随机变量与 transcript ​

固定输入分布 $\mu$，令 $(X,Y)\sim \mu$。随机协议使用公共币 $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；相关输入时结论可能改变。

一 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 付费。

信息成本不超过通信 ​

对 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 消息对另一项同理；把各轮贡献求和不超过发送长度。

于是任何信息成本下界都会给通信下界。反向等号不必成立：随机 padding、重复消息和双方已知的相关信息都能增加通信而不增加相同数量的信息成本。

函数的信息复杂度 ​

在分布 $\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，应把合法协议集合改成逐输入错误约束，不能默认由平均错误替代。

信息复杂度特别适合追踪多轮对话中知识怎样逐步转移，但具体函数下界仍需证明任何正确 transcript 都泄露足够信息。仅写互信息公式不会自动产生正下界。

边界与 convention ​

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

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

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

参考资料

• 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.