摊销通信复杂度

极限为什么存在，而不只是一个希望 ​

把一个 $n$ 副本协议与一个 $m$ 副本协议串接，就得到 $n+m$ 副本协议；原有的每坐标错误要求仍成立。因此

这是次可加性。由于输入集合有限，总能发送全部必要输入，故 $C_n$ 有线性上界且非负。次可加序列的极限定理给出

也可以直接看懂这一点：选择一个长度为 $k$ 的高效批次，反复拼接它处理任意大批量；最后不足 $k$ 个副本的尾部用朴素协议处理，尾部成本除以总副本数后趋于零。

所以摊销复杂度是一切有限批次单位成本的下确界。它不要求 $C_n/n$ 随 $n$ 单调，也不保证某个固定批量已经达到极限。

下界方向：信息不能凭批量执行而消失 ​

对任意协议，内部信息成本不超过通信长度。若一个协议完成 $n$ 个独立副本，信息直接和论证还给出

在每坐标错误要求下成立。故 $C_n\ge n{\mathrm{IC}}_{\mu }(f,\rho )$，除以 $n$ 再取极限，即得 ${\mathrm{AC}}_{\mu }\ge {\mathrm{IC}}_{\mu }$。

这一步的机制是互信息链式分解与坐标嵌入。链式分解把关于输入向量的信息摊到坐标；嵌入则用多副本协议构造一个单副本协议，使其平均信息成本至多为总成本的 $1/n$。相关输入对的模拟需要适当的条件分布，不能把两方的输入分别独立抽样后假装仍服从 $\mu$。

若采用平均坐标错误的定义，还可以结合错误预算下信息复杂度的凸性，或直接使用随机置换化为前面的形式。这些是定理中的实质步骤，并非仅凭“熵具有可加性”就已完成证明。[1][2]

上界方向：为什么必须留下正的错误余量 ​

给定目标错误率 $\rho >0$，先选一个稍严格的 ${\rho }^{\prime }<\rho$，再选单副本协议 $\pi$，使其信息成本接近 ${\mathrm{IC}}_{\mu }(f,{\rho }^{\prime })$。独立运行它的 $n$ 份副本，会产生可以联合压缩的消息结构。

联合压缩并非把某一方的消息直接交给普通压缩器。交互中，消息的条件分布部分取决于发送方输入，接收方却拥有另一份相关信息。协议压缩公理库交互协议压缩Interactive protocol compression · Interactive compression利用 transcript 的内部信息成本模拟交互协议，并区分单次期望通信、轮数损失与多副本摊销极限。要让双方协同重现这些消息，并支付协调所需的开销。

对固定的单副本协议，独立副本的信息密度之和在大批量下集中在其均值附近。压缩后的主要成本因而接近

为了保持最坏长度上限，证明还要设置硬截断：通信到达预算时停止，输出预定结果。截断事件与模拟失败事件在输入分布下的概率可以做得很小，并由 $\rho -{\rho }^{\prime }$ 这份余量吸收。这样才能从一个典型情况下很短的模拟，得到定义所要求的“所有执行都有长度上限”的协议。

最后让 ${\rho }^{\prime }\uparrow \rho$，并使单副本近似误差趋于零。有限输入下，信息复杂度在正错误参数处具有所需的连续性；一个直观原因是，利用公开随机数，以很小概率改为发送全部输入并精确计算，就能小幅降低错误率，而信息代价也仅小幅增加。[1]

因此正容错参数不是装饰：它用于吸收模拟与截断的额外错误。零错误端点必须单独分析，不能把这段证明直接令 $\rho =0$。

每坐标错误、平均坐标错误与整批错误 ​

这里每个坐标都允许错误概率 $\rho$。一个近似的写法是只要求

在当前独立同分布副本与公开随机数模型中，这两种要求有相同的最优成本：对满足平均要求的协议，先公开随机置换坐标，执行协议后再把输出恢复原序。输入分布不变，每个原坐标都均匀分担原来的错误率，而通信上限不增加。

但是，“整批所有答案同时正确的概率至少为 $1-\rho$”是另一个更强的要求。每坐标错误为 $\rho$ 只直接给出整批失败概率至多 $n\rho$；即使各坐标错误独立，整批成功率也可能是 $(1-\rho {)}^n$。

允许少量坐标出错，类似有损压缩中的平均失真；要求整批一个都不出错，则涉及更严格的块错误控制。二者不能共用一个未注明口径的“误差 $\rho$”。

一个精确可算的例子：传输公平比特的失真率 ​

令 Bob 没有输入，Alice 持有公平比特 $X$，任务是让 Bob 估计它。对单次任务，只要要求错误率小于 $1/2$，零通信就不够；发送 $X$ 一位即可，所以单次最坏通信成本为一。

但它的信息复杂度在允许错误率 $0<\rho <1/2$ 时是

下界来自 Fano 不等式：要把公平比特的错误率压到 $\rho$，观察后剩余条件熵至多为 $h_2(\rho )$。上界则有具体协议：Alice 取独立噪声 $N\sim \mathrm{Bernoulli}(\rho )$，发送 $T=X\oplus N$，Bob 输出 $T$。错误率为 $\rho$，且

虽然这个单次协议仍发送一位，其内部信息小于一位。大量独立比特可以通过有损块编码，把每位通信降到 $1-h_2(\rho )$ 的极限。这是等价定理在单向情形中的具体图像：副本联合编码，把整数长度与单次编码开销分摊掉。

例如 $\rho =0.1$ 时，极限约为 $0.5310$ 比特／副本。这个小数是大批量总长度除以副本数，不意味着一次物理通信可以发送半个比特。

零错误端点：平均长度与硬上限会分道扬镳 ​

再看 $X\sim \mathrm{Bernoulli}(1/4)$，仍要求 Bob 恢复 $X$。单次零错误信息成本为

然而，若要求整批协议零错误，并且最坏长度有硬上限，则每个 $n$ 位输入串都以正概率出现，必须被完全区分。零错误随机性也不能改变这一计数事实：对有限个输入，同时正确的随机带集合仍有概率一；固定其中一条随机带便得到零错误确定性协议。至少 $2^n$ 个不同输入需要 $2^n$ 个可区分叶子，因此最坏长度至少为 $n$。

于是这个模型下

若改用期望码长，前缀编码可以使 $n$ 个副本的期望长度接近 $nH(X)$，单位成本又趋于 $H(X)$。所以零错误结论的差异来自成本定义，不是熵的矛盾，更不意味着正错误率的等价定理失效。

与直接和、直接积分别有什么关系 ​

直接和公理库通信复杂度的 Direct Sum 与 Direct ProductDirect sum in communication complexity · Direct product in communication complexity比较同时求解 k 个独立实例所需的总通信，并研究通信不足时全部成功概率是否指数下降。关注多副本总成本相对于单副本成本如何增长；摊销复杂度则追问增长的最优线性系数。由于单次通信可能比信息成本大，不能从“信息等于摊销”直接推出对所有任务都有 $C_n\approx n{C}_1$。

直接积主要研究资源不足时整批成功率下降得多快，常常采用所有坐标同时正确的成功事件。它与每坐标分布错误率下的摊销模型相邻，却不是同一个结论。

实际阅读一条摊销定理时，最有用的核对是：输入对是否按乘积副本生成，错误保证按坐标还是按整批，成本取最坏还是期望，以及由谁输出。只有这些约定一致，单位成本与信息量的等式才有明确含义。

固定输入分布下的成本与错误约定属于分布通信复杂度公理库分布通信复杂度Distributional communication complexity固定输入分布后，以确定性协议在该分布下的平均错误衡量通信，是随机最坏复杂度的分布侧接口。模型；不能未经论证改成对每个输入取最坏值的要求。