信息复杂度 | Codeboy's Blog

Alice 和 Bob 为完成一个任务交换消息。通信复杂度按消息长度衡量“线上传了多少位”，信息量则衡量“这些消息使输入的不确定性减少了多少”。

信息复杂度研究：完成一个分布明确的通信任务，至少必须揭示多少输入信息。它既是通信下界的工具，也解释了为什么很多独立任务合在一起执行时，平均通信量可能低于逐个执行的成本。[1][2]

形式陈述

先确定观察者拥有什么信息

设有限输入对 $(X,Y)$ 服从已知联合分布 $\mu$ ，Alice 只持有 $X$ ，Bob 只持有 $Y$ ；不要求两者独立。公开随机串 $R$ 独立于整个输入对。双方的私有随机带 $A,B$ 相互独立，也独立于 $(X,Y,R)$ 。本文先取深度有统一有限上界的二进制协议：谁发言、何时结束均由 $R$ 和已经公开的消息前缀决定；发送内容只依赖发送者的本地视图。记完整消息记录为 $T$ ，不把未发送的私有随机带直接算作公开消息。所有对数以二为底，信息量的单位为比特。

这里的条件信息量也允许把整条随机带放在条件中。对有限随机变量 $U$ ，定义

H(U\mid C)=E_C\!\left[-\sum_u\Pr(U=u\mid C)\log_2\Pr(U=u\mid C)\right], \qquad I(U;V\mid C)=H(U\mid C)-H(U\mid V,C).

$C,V$ 可以包含无限公平随机带，条件概率取通常随机带空间上的条件分布。有限 $U$ 保证这些熵有限；所用离散条件熵恒等式可先对条件分布计算，再平均。本文每个互信息项至少有一侧是有限输入或有限 transcript，这一约定也涵盖含私有带的链式分解。

协议 $\pi$ 的内部信息成本定义为

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

第一项从 Bob 的角度计算：他已经知道 $Y,R$ ，消息又使他得知多少关于 $X$ 的新信息。第二项从 Alice 的角度计算。两项条件变量不同，因此不能把它们简单解释成“每个消息的熵加了两遍”。

外部信息成本则是

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

这是一个知道公开随机数、却原本不知道双方输入的外部观察者，从消息中学到的输入信息。把 $R$ 作为条件，是为了准确反映观察者已经知道什么，而不是给随机种子本身收费：由于 $R$ 与输入独立， $I(T,R;X,Y)=I(T;X,Y\mid R)$ 。

只计算 $I(T;X,Y)$ 则可能漏算信息。例如 Alice 发送 $T=X\oplus R$ ，其中 $X,R$ 是独立公平比特；单看 $T$ 不透露 $X$ ，知道公开的 $R$ 后却能完整恢复 $X$ ，外部信息为一 bit。私有随机数影响消息的分布，却不因存在于本地就自动计入通信量。

Bob 实际还知道私有带 $B$ ，所以他的完整学习量应写成 $I(T;X\mid Y,R,B)$ 。下文将证明它恰好等于定义中的 $I(T;X\mid Y,R)$ ；Alice 的情形对称。这个等价来自合法协议的结构，并不适用于任意人为指定的随机变量 $T$ 。

从一个协议，转到一个任务的最优成本

设 $f:\mathcal X\times\mathcal Y\to\mathcal Z$ ，并明确要求 Bob 输出答案。对固定输入分布 $\mu$ 与允许错误率 $\rho$ ，定义

\operatorname{IC}_\mu(f,\rho) =\inf_{\pi:\Pr_{(X,Y)\sim\mu,\,\pi}[\pi(X,Y)\ne f(X,Y)]\le\rho} \operatorname{IC}^{\mathrm{int}}_\mu(\pi).

概率同时平均输入与协议随机性；它是分布错误率，不要求每个输入上的错误率分别不超过 $\rho$ 。取下确界是因为最优成本未必由某个有限协议达到。

若 $D^\mu_\rho(f)$ 表示在相同分布错误要求下最小的最坏通信长度，则直接得到

D^\mu_\rho(f)\ge\operatorname{IC}_\mu(f,\rho).

改变协议要求会改变优化问题。例如要求双方都知道答案、要求每个输入都达到成功率，或把成本改为平均长度，都需要重新定义可选协议与成本。特别是

\sup_\mu\inf_\pi(\cdots) \quad\text{与}\quad \inf_\pi\sup_\mu(\cdots)

表示不同的选择顺序，不能在没有相应定理时直接互换。说一个函数“信息复杂度是 $I$ ”，应交代分布、错误标准、输出方和内部／外部的口径。

直觉

为什么信息成本给出通信下界

先补齐私有随机性下的关键结构。固定输入 $x,y$ 、公开随机串 $r$ 和一个公开前缀 $t$ 。沿着该前缀，把 Alice 每次发言与 $t$ 一致所要求的私有带收集为集合 $\mathcal A(x,r,t)$ ，把 Bob 的相应要求收集为 $\mathcal B(y,r,t)$ 。由于轮次和终止规则公开，每一步只给当前发送者的随机带增加一个约束，因而

\{\text{执行到达前缀 }t\} =\{A\in\mathcal A(x,r,t)\}\cap\{B\in\mathcal B(y,r,t)\}.

空前缀时两个集合都是整个随机带空间；追加 Alice 的一 bit 时只缩小第一个集合，追加 Bob 的一 bit 时只缩小第二个。这也给出了按前缀长度的归纳证明。由独立随机带，前缀的条件概率分解为 $a(x,r,t)b(y,r,t)$ ，其中两个因子分别是上述集合的概率。这里分解的是给定输入后的协议概率，没有假设原输入分布 $\mu$ 是乘积分布。

在正概率条件下，给定 $x,y,r,t$ 后， $A$ 的条件分布就是其原分布限制到 $\mathcal A(x,r,t)$ 并归一化；分子、分母中的 Bob 因子消去，所以这个分布不再依赖 $y$ 。若接下来由 Alice 发言，消息 $M$ 是 $(x,r,t,A)$ 的函数，因此

M\perp Y\mid X,R,T_{<i}.

这一步允许 Alice 重复使用同一条私有带，保留任意本地随机记忆；无需假装每轮都重新抽独立随机币。Bob 发言时对称地有 $M\perp X\mid Y,R,T_{<i}$ 。

完整 transcript 也满足同一分解，所以 $B$ 给定 $(X,Y,R,T)$ 后的分布只依赖 $(Y,R,T)$ ，即 $I(B;X\mid Y,R,T)=0$ 。再由随机带的初始独立性，链式法则给出

\begin{aligned} I(T,B;X\mid Y,R) &=I(T;X\mid Y,R)+I(B;X\mid Y,R,T)\\ &=I(T;X\mid Y,R),\\ I(T,B;X\mid Y,R) &=I(B;X\mid Y,R)+I(T;X\mid Y,R,B)\\ &=I(T;X\mid Y,R,B). \end{aligned}

这就证明了前面的完整视图解释，也为后面向 Bob 的视图应用 Fano 不等式准备了依据。

把局部学习量沿协议树相加

对标准二方协议，内部信息不超过外部信息，而外部信息不超过期望通信长度：

\boxed{ \operatorname{IC}^{\mathrm{int}}_\mu(\pi) \le\operatorname{IC}^{\mathrm{ext}}_\mu(\pi) \le E_\mu[|T|] \le\operatorname{CC}(\pi). }

最后一个量是所有输入与随机选择上的通信长度上界。对每个固定 $R=r$ ，完整记录是协议树的叶子，构成前缀无歧义编码；Kraft 不等式的前缀集合版本允许唯一的空记录，也给出 $H(T\mid R=r)\le E[|T|\mid R=r]$ 。对 $R$ 平均，再用 $I(T;X,Y\mid R)\le H(T\mid R)$ ，便得到外部信息不超过期望长度。不能把终止时间当作免费、不计成本的额外信道。[2][3]

内部不超过外部这一结论也值得理解其机制。假设当前轮由 Alice 发消息 $M$ ，此前记录为 $T_{<i}$ 。刚刚证明的条件独立性保证

I(M;Y\mid X,R,T_{<i})=0.

内部成本在这一轮只留下 Bob 的学习量 $I(M;X\mid Y,R,T_{<i})$ 。外部增量按链式法则等于

I(M;X,Y\mid R,T_{<i}) =I(M;Y\mid R,T_{<i})+I(M;X\mid Y,R,T_{<i}).

第一项非负，因此本轮外部增量不小于内部增量。对 Bob 发言的轮次对称处理，再用互信息链式分解相加即可。严格地说，可把提前结束的路径补到统一深度：终止后填入由前缀已确定的符号 $\bot$ ，它的新增信息为零；每个未终止前缀按其公开指定的发送者使用上述计算，再对前缀取平均。有限深度保证这是有限求和。这样比较的是每次消息带来的新增信息，而不是错误地假设“条件越多，互信息一定越小”。

关键前提是 $T$ 来自合法的交互协议。对任意随机变量，条件化可能增加互信息，两项条件互信息之和完全可能大于联合互信息；下文的异或输出就是反例。不能把针对 transcript 的定理当作无条件的信息论代数恒等式。

若允许无统一深度上界的协议，需要另行处理截断与极限，并保持公开终止规则。这里的证明不把“期望长度有限”当作一切极限交换自动成立的理由。

例子与边界

AND：同一棵树上的五种数值

令 $X,Y$ 为独立公平比特，要求双方都知道 $U=X\land Y$ 。Alice 先发送 $X$ ；若为零，双方立即输出零；否则 Bob 再发送 $Y$ ，双方输出这个值。这就是协议树与 transcript中的三叶协议，确定性协议也属于允许随机性的协议类。

输入 $(X,Y)$	概率	完整记录 $T$	长度 $\lvert T\rvert$	输出 $U$
$(0,0)$	$1/4$	`0`	$1$	$0$
$(0,1)$	$1/4$	`0`	$1$	$0$
$(1,0)$	$1/4$	`10`	$2$	$0$
$(1,1)$	$1/4$	`11`	$2$	$1$

完整记录的概率分别是 $1/2,1/4,1/4$ 。它是输入的确定函数，因此 $H(T\mid X,Y)=0$ ，外部信息成本等于

I(T;X,Y)=H(T) =-\frac12\log\frac12-2\cdot\frac14\log\frac14 =\frac32.

内部成本则要分别站在两位接收者的位置计算。无论走到哪个叶， $T$ 的首位都给出 $X$ ，所以 $H(X\mid Y,T)=0$ 。当 $X=0$ 时，记录恒为 0，公平比特 $Y$ 完全没有被揭示；当 $X=1$ 时，第二位完整揭示 $Y$ 。于是

H(Y\mid X,T)=\frac12\cdot1+\frac12\cdot0=\frac12.

接收者及未知输入	通信前条件熵	通信后条件熵	学到的信息
Bob 学习 $X$ ，已知 $Y$	$H(X\mid Y)=1$	$H(X\mid Y,T)=0$	$1$
Alice 学习 $Y$ ，已知 $X$	$H(Y\mid X)=1$	$H(Y\mid X,T)=1/2$	$1/2$

因此 $\operatorname{IC}^{\mathrm{int}}_\mu(\pi)=1+1/2=3/2$ 。这里第二项的 $1/2$ 是对全部输入平均：Bob 真正发言时发送一整位，但到达他的结点的概率只有一半。

独立公平输入的 AND 协议有三片叶：记录 0、10、11 的概率为二分之一、四分之一、四分之一；平均通信与两种信息成本均为 1.5 bit，最坏通信为 2 bit。 — AND 协议的信息成本

最终输出把 0 与 10 两条不同记录合并为同一个零。由于 $\Pr(U=1)=1/4$ ，输出熵为

H(U)=h_2(1/4)=2-\frac34\log_2 3\approx0.811278.

甚至把输出代入内部成本公式也会得到不同的数：给定 $Y=0$ ， $U$ 恒为零；给定 $Y=1$ ， $U=X$ ，所以 $I(U;X\mid Y)=1/2$ ，对称项也是 $1/2$ ，两项合计为一。输出既不是完整记录，输出熵也不是这次对话的信息成本。

所选 AND 协议的量	数值（bit）	计算依据
最坏通信 $\operatorname{CC}(\pi)$	$2$	最深叶的深度
平均通信 $E\lvert T\rvert$	$3/2$	$(1/2)\cdot1+(1/2)\cdot2$
外部信息 $\operatorname{IC}^{\mathrm{ext}}_\mu(\pi)$	$3/2$	$H(T)$
内部信息 $\operatorname{IC}^{\mathrm{int}}_\mu(\pi)$	$3/2$	$1+1/2$
输出熵 $H(U)$	$\approx0.811278$	$h_2(1/4)$

这完整算出了一个协议的成本。它没有证明该协议在所有合法协议中信息成本最小，因而不能直接宣称 AND 的最优信息复杂度就是 $3/2$ 。前面的任务定义默认 Bob 输出；此例特意要求双方输出，使三片叶均有双方可知的答案。

三个协议，把内部与外部信息分开

发送一个未知比特。设 $X,Y$ 是独立公平比特，Alice 发送 $T=X$ 。Bob 学到完整的一位 $X$ ，Alice 没有获得关于 $Y$ 的新信息，所以

\operatorname{IC}^{\mathrm{int}}_\mu(\pi)=1+0=1, \qquad \operatorname{IC}^{\mathrm{ext}}_\mu(\pi)=1.

若消息改为 $X$ 后接一千个固定的零，两种信息成本仍为一，通信长度则是一千零一。信息量只关注输入相关的变化，而不是编码的冗余长度。

重复对方已经知道的比特。设 $X=Y$ ，共同取一个公平比特，Alice 仍发送 $X$ 。Bob 原本就知道它，Alice 也没有得到新信息，因此内部成本为零；外部观察者却从消息中知道了一位输入信息，所以外部成本为一。

这个例子同时说明，零内部信息并不意味着实际协议不发送消息。它还揭示了优化协议的必要性：若任务只是让 Bob 输出 $X$ ，在这个输入分布下根本不必通信。多余发送属于所选协议的浪费，不是任务本身的必需成本。

只看输出，会漏掉计算它的过程。令 $X,Y$ 独立公平，目标是让 Bob 输出 $X\oplus Y$ 。Alice 发送 $X$ 后，Bob 可以本地计算，通信与内部信息均为一。若把最终结果 $U=X\oplus Y$ 错当成完整消息记录，则

I(U;X\mid Y)+I(U;Y\mid X)=2, \qquad I(U;X,Y)=1.

这里 $U$ 只是函数输出，并不是上述协议的完整 transcript。输出含有多少信息，与双方为了产生输出必须交换多少信息，是不同的问题。

内部信息扣除每位参与者原本知道的输入；外部信息只扣除公开随机数。消息记录 T 不包含未公开的私有随机种子。

一个可以完整推出的下界：恢复未知输入

若任务要求 Bob 恢复有限集合 $\mathcal X$ 中的 $X$ ，其中 $|\mathcal X|\ge2$ ，并且错误概率至多为 $0\le\rho<1/2$ ，Fano 不等式把恢复精度转化为剩余不确定性上界。即使随机带无限，也可先固定 $(R,B)=(r,b)$ ，对有限观察量 $(Y,T)$ 使用离散 Fano 不等式。记此时的实际错误为 $p_{r,b}$ ；对随机带平均，再用Jensen 不等式处理凹函数 $h_2(p)$ ，得到 $H(X\mid Y,T,R,B)\le h_2(p)+p\log(|\mathcal X|-1)$ ，其中 $p=E[p_{r,b}]\le\rho$ 。该右端在 $0\le p\le\rho<1/2$ 单调增加。结合随机带的初始独立性与前面的私有视图等价式，可得

I(T;X\mid Y,R) \ge H(X\mid Y)-h_2(\rho)-\rho\log(|\mathcal X|-1),

其中 $h_2(\rho)=-\rho\log\rho-(1-\rho)\log(1-\rho)$ 。公开随机数独立于输入，所以开始时的不确定性是 $H(X\mid Y)$ ，而不是 $H(X\mid Y,R)$ 中另一个不同数值。[4]

例如 $X$ 为均匀的 $k$ 位串，Bob 没有相关输入，并要求完全恢复，则 $\rho=0$ ，内部信息至少为 $k$ ，通信也至少为 $k$ 。若 Bob 的 $Y$ 已经确定了 $X$ ，则初始条件熵为零，这一恢复任务无需揭示新信息。

这条论证对“恢复整个输入”很有效，却不能把一般函数 $f(X,Y)$ 都当成恢复 $X$ 。计算一个低熵答案也可能需要很高的信息成本；必须证明协议过程中某些输入信息不可避免地被学到，而不是只计算答案的熵。

推论与应用

独立副本为何适合用信息量分析

考虑 $n$ 对独立输入 $(X_i,Y_i)\sim\mu$ ，双方可以交错地处理所有副本。消息不一定属于某一个坐标，逐位计算通信成本因而很难；互信息却有链式分解，可以把有关整组输入的信息展开为条件信息之和。

严谨的直接和论证再配合坐标嵌入：选择一个坐标作为真实输入，把其他坐标按适当的条件分布模拟，从多副本协议构造单副本协议。这里每对内部的 $X_i,Y_i$ 可以相关，独立的是不同输入对。不能把链式分解中的条件直接删去，也不能假定 Alice 能独自生成 Bob 的相关输入。[2]

在固定有限输入分布、正的每坐标允许错误率及匹配的输出约定下，这种下界与多副本协议压缩合起来，得到

\operatorname{IC}_\mu(f,\rho) =\text{大量独立副本的极限平均通信成本}.

精确定义、错误率留余量与最坏长度截断见摊销通信复杂度。这是一条关于批量极限的操作解释，不等于“单次最优通信必然等于信息量”。分布通信中，单次成本和内部信息复杂度之间可以存在很大的分离。[3]

下界与压缩的两种用法

设计信息下界时，通常先选一个使任务困难、同时便于分析的输入分布；再从正确性推出某种必须减少的不确定性，利用互信息或统计距离把它定量化；最后通过“信息不超过通信”得到下界。DISJ 的完整信息论证明从 AND 的私有输出、消息因子分解和 Hellinger 距离推出显式正常数，再用条件熵直和与逐坐标本地嵌入得到线性界。其成本是条件外部信息，正确性要求覆盖全部输入；不能把它直接代入上面的分布错误、内部信息摊销定理。

设计压缩协议时，方向相反：先说明原协议在接收方已有信息之外究竟揭示了多少，再研究双方如何用更短通信协同重现消息分布。普通熵编码不能直接解决任意交互压缩，因为编码所需的条件分布可能分别掌握在两方手中。

参考资料

[1] Anup Rao and Amir Yehudayoff, Communication Complexity: and Applications, Cambridge University Press, 2020，信息复杂度相关章节。

[2] Mark Braverman and Anup Rao, “Information Equals Amortized Communication”, IEEE Transactions on Information Theory 60(10), 6058–6069, 2014。作者预印本，所查 21 页稿第 3.2 节、印刷页 6–9，特别是 Lemmas 3.13–3.14 的信息成本与逐 bit 论证；批量解释见其直接和与摊销部分。

[3] Anup Rao and Makrand Sinha, “Simplified Separation of Information and Communication”, 2015。15 页作者稿，第 1 页定义与第 3.6 节、印刷页 7 的 Propositions 15–16。该处关于条件输入独立性的命题有乘积分布与确定性假设；本文一般相关输入、私有带的结论由上面的前缀事件分解单独证明。

[4] Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006，条件互信息、数据处理与 Fano 不等式。

形式陈述 ​

先确定观察者拥有什么信息 ​

从一个协议，转到一个任务的最优成本 ​

为什么信息成本给出通信下界 ​

把局部学习量沿协议树相加 ​

AND：同一棵树上的五种数值 ​

三个协议，把内部与外部信息分开 ​

一个可以完整推出的下界：恢复未知输入 ​

独立副本为何适合用信息量分析 ​

下界与压缩的两种用法 ​

反向链接