误差压缩定理的证明

错误证明（第 132 页倒数第七行附近，定理 4.2 的证明）

定理陈述无误，原证明有误。原证明令 \(X_i\) 表示第 \(i\) 次重复运行是否输出 1。对于 \(x\notin L\)，只能得到

\[ \mathsf{E}[X]\leq k\bar p. \]

此时使用 Chernoff 上尾界得到形如

\[ \Pr[\cdots]\leq e^{-\delta^2\mathsf{E}[X]/3} \]

的估计。然而 \(e^{-t}\) 关于 \(t\) 单调递减，由 \(\mathsf{E}[X]\leq k\bar p\) 实际得到的是

\[ e^{-\delta^2\mathsf{E}[X]/3} \geq e^{-\delta^2k\bar p/3}. \]

因此，原证明随后用于压低错误概率的不等号方向错误，不能成立。

定理 4.2（误差压缩定理）

\[ \operatorname{Err}(2^{-n^d}) = \operatorname{Err}\!\left(\frac12-\frac1{n^c}\right), \qquad c,d>0. \]

证明： 正向包含

\[ \operatorname{Err}(2^{-n^d}) \subseteq \operatorname{Err}\!\left(\frac12-\frac1{n^c}\right) \]

是显然的：对充分大的 \(n\)，有 \(2^{-n^d}<1/2-n^{-c}\)；有限个短输入可以硬编码处理。

下面证明反向包含。设 \(L\in\operatorname{Err}\!\left(1/2-1/n^c\right)\)，原算法 \(\mathbb{P}\) 对每个长度为 \(n\) 的输入 \(x\) 满足

\[ \Pr[\mathbb{P}(x)\text{ 正确}] \geq \frac12+\frac1{n^c}. \]

记 \(\varepsilon=n^{-c}\)。独立运行 \(\mathbb{P}\) 共 \(k\) 次并取多数票，所得算法记为 \(\mathbb{P}'\)，其中 \(k=2\left\lceil 2n^{2c+d}\right\rceil+1.\) 令

\[ X_i= \begin{cases} 1,&\text{第 }i\text{ 次运行结果正确},\\ 0,&\text{否则}. \end{cases} \]

我们考虑 \(X=\sum_{i=1}^kX_i, \mu=\mathsf{E}[X].\) 则无论 \(x\in L\) 还是 \(x\notin L\)，都有统一的下界

\[ \mu\geq k\left(\frac12+\varepsilon\right). \]

多数票出错蕴含 \(X\leq k/2\)。定义

\[ \delta=1-\frac{k}{2\mu}, \]

则 \(0<\delta<1\) 且 \((1-\delta)\mu=k/2\)。又因为 \(\mu\geq k(1/2+\varepsilon)\)，所以

\[ \delta \geq 1-\frac1{1+2\varepsilon} = \frac{2\varepsilon}{1+2\varepsilon} \geq \varepsilon, \]

其中最后一个不等式对充分大的 \(n\) 成立，此时 \(\varepsilon\leq 1/2\)。使用 Chernoff 界，

\[ \begin{aligned} \Pr[\mathbb{P}'\text{ 出错}] &\leq \Pr[X\leq(1-\delta)\mu]\\ &\leq e^{-\delta^2\mu/2}\\ &\leq e^{-\varepsilon^2k/4}. \end{aligned} \]

因为 \(k>4n^{2c+d}\) 且 \(\varepsilon^2=n^{-2c}\)，所以

\[ \Pr[\mathbb{P}'\text{ 出错}] <e^{-n^d} <2^{-n^d}. \]

有限个短输入仍可硬编码处理。因此

\[ \operatorname{Err}\!\left(\frac12-\frac1{n^c}\right) \subseteq \operatorname{Err}(2^{-n^d}), \]

从而结论成立。

致谢

感谢陈晗同学在 2024 年秋季学期的课上指出了这个问题。