轮消除引理

Alice 的首消息 $M$ 在看到 $m$ 份 $x_j$ 后发出，却不知道 Bob 的目标索引 $i$。用互信息公理库互信息Mutual information一个随机变量对另一个随机变量不确定性的平均减少量。度量它对坐标的泄露；若 $X_j$ 独立，则

Bob 已知 $X_{<i}$，所以随机坐标的条件信息平均至多 $a/m$。当 $m=Ra$ 时，这只是常数 $1/R$；平均编码与 Pinsker 型估计说明，针对目标 $X_i$ 的首消息分布接近一个不依赖 $X_i$、可由公共币采样的分布。Bob 先公开采样这条“伪首消息”，协议便从原第二条消息开始。

原 MNSW 证明以分布限制和概率估计完成这一步；现代语言可把它视为交互压缩公理库交互协议压缩Interactive protocol compression · Interactive compression利用 transcript 的内部信息成本模拟交互协议，并区分单次期望通信、轮数损失与多副本摊销极限。中的首消息低信息模拟。这只是特化的 one-shot 步骤，不表示任意多轮协议都能在保持 round 和最坏通信时压到其总信息成本。

取 $a=1$、$m=4256$，首消息只有一 bit。链式法则保证存在坐标 $i$ 使

若 bit 以底二互信息计，Pinsker 给平均 total variation 至多

因此用不看 $X_i$ 的边缘分布替换首消息，只把该坐标协议的平均错误增加不到百分之一量级。固定错误引理先将原协议并行重复 $99$ 次并多数表决，再应用可变错误版本；这解释了 $C=99$，而不是把误差损失偷偷忽略。

若 Alice 知道 $i$，她的一 bit 可以全部描述目标坐标，$a/m$ 平均论证立即失效。若 $X_j$ 高度相关，其他坐标可能泄露 $X_i$；若 Bob 没有声明的前缀 side information，仍有较弱版本，但不能反过来把强版本的条件变量删除。MNSW 还明确指出同样形式的 deterministic 引理并未由其证明覆盖。

对具有自归约 $P_m(f_{n^{\prime }})\to f_n$ 的问题，可交替应用角色互换版本，每次删一条消息并更新问题规模。若经过 $t$ 次仍保持非平凡输入，却得到零消息、错误小于 $1/2$ 的协议，便产生矛盾；这给 predecessor、Greater-Than 及指针追逐公理库指针追逐通信问题Pointer chasing communication problem · Pointer jumping problem双方交替持有二部图两侧的指针函数，追踪固定起点的第 k 个顶点以显露起始方与轮数的价值。型问题的 round-sensitive 下界。

引理不是任意函数的黑箱总通信下界：必须另外提供自归约，并逐步核算 $a,b$ 的常数放大、错误与规模。只迭代“轮数减一”而不检查问题参数是否仍非退化，可能在到达零轮前已经把输入缩成常数。