形式陈述

设随机算法每次独立运行都以概率至少 $1/2+\delta$ 输出正确答案，其中 $\delta >0$。独立运行 $r$ 次并取多数票，令 $X_i$ 指示第 $i$ 次出错；Hoeffding/Chernoff 界给

$$\text{Pr}[\sum _{i=1}^r{X}_i\ge r/2]\le e^{-2{\delta }^{2}r}.$$

因此把常数错误降到 $\epsilon$ 只需 $r=O({\delta }^{-2}\log \left(1/\epsilon \right))$。BPP 用多数票；RP 的单侧错误通常重复后取“任一次接受”。独立性可由每轮使用新随机位保证。

直觉

只要单次正确率稳定高于一半，多次独立样本的平均会集中在真实偏向附近；多数结果同时出错需要异常大的统计波动。

例子与边界

单次正确率 $2/3$ 时，重复 $O(\log n)$ 次可把长度 $n$ 输入上的错误降到 $n^{-c}$。重复并不会修复有系统偏差、正确率恰为 $1/2$ 或高度相关的试验。多数次数取奇数可避免平票；即使取偶数，也必须明确平票规则并计入界中。

推论与应用

概率放大说明 BPP、RP 等类的具体常数阈值不重要，只要与 $1/2$ 保持常数间隔即可。密码学中也用独立重复或并行重复降低失败概率，但交互协议的并行重复可能需要额外定理，不能机械套用独立伯努利分析。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 7, error reduction for randomized computation。
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995，Ch. 4, tail inequalities and amplification by repetition。