概率放大

只要单次正确率稳定高于一半，多次独立样本的平均就会集中在真实偏向附近，多数结果同时出错需要异常大的统计波动；概率放大由此把固定优势转化为指数小误差。不过聚合规则取决于误差类型：双边误差用多数票抵消两侧噪声，RP 型单边误差用 OR，coRP 型用 AND，零错误算法则通常通过重启降低超时概率。真正提供指数衰减的是独立性或足够弱相关性加上常数偏差。

单次正确率 $2/3$ 时，三次独立运行的多数错误率可直接展开为 $(\genfrac{}{}{0ex}{}{3}{2})(1/3{)}^2(2/3)+(1/3{)}^3=7/27$，小于原来的 $1/3$。一般地 $\delta =1/6$，上面的尾界为 $e^{-r/18}$，对整数 $n\ge 2$ 与固定 $c>0$，选不小于 $18c\ln n$ 的奇数 $r$，便把长度 $n$ 输入上的错误压到 $n^{-c}$；若要降到 $2^{-n}$，取 $O(n)$ 次仍为多项式。RP 的单次漏报至多 $1/2$，重复 $k$ 次后采用“任一次接受即接受”，漏报直接变为 $2^{-k}$。重复不会修复系统偏差、正确率恰为 $1/2$ 或高度相关的试验；多数次数取奇数可避免平票，取偶数则必须明确规则并计入界中。

若各轮复用完全相同随机种子，重复结果相同，误差不会下降。偏差仅为 $2^{-n}$ 时需要指数次数才能形成常数信号；对 RP 直接使用多数票仍保持零假阳性，但没有充分利用单边结构；采用“至少一次接受即接受”的 OR 规则，可把漏报率更直接地降为 $2^{-k}$。

在学习问题中，重复运行能否降低 失败概率 $\delta$理路样本复杂度、精度与置信度Sample complexity · Accuracy and confidence用 m(ε,δ) 描述达到风险精度与失败概率所需的数据量。 取决于输出能否验证或安全聚合。若有独立验证集，可从多个预测器中选择；对二元分类也可在附加条件下多数投票。任意回归器的参数平均、看不到真实风险的 learner 或高度相关的训练样本都不能无条件沿用 BPP 多数表决。若要让有限假设类的所有坏事件同时不发生，还应先把每个事件失败率压到约 $\delta /|H|$，再使用并集界，而不是把并集本身误称为独立重复。

概率放大说明 BPP 的具体常数阈值不重要，只要正确率高于 $1/2$ 一个常数间隔。RP 的 OR 放大则只需要正实例上的接受率有正的常数下界，不要求超过 $1/2$；即使接受率为 $1/10$，重复 $r$ 次后的漏报率也至多为 $(9/10{)}^r$。Chernoff 方法理路Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds从指数矩与 Markov 不等式推导尾界，给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。解释双边多数票的指数衰减；单侧错误则由独立事件概率直接相乘。它让BPP理路复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。、RP理路复杂度类 RPComplexity class RP具有单边误差多项式时间随机算法的语言类。等定义中的常数具有鲁棒性，也能在多项式次 union bound 前把单次失败压到逆多项式或可忽略水平。

在亚线性模型中，重复的代价必须记回原资源。随机通信协议理路随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。重复 $r$ 次通常把通信量乘 $r$，并行执行还需单独报告轮数；随机查询算法理路确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity以决策树和量词定义确定性、允许错误与零错误查询成本，用 OR、奇偶与带间隔多数解释随机化的作用。会增加查询次数，复用相同随机查询则未必独立；性质测试器理路单侧与双侧性质测试器One-sided property tester · Two-sided property tester按性质内对象是否永不被拒绝，区分 perfect completeness 的单侧测试与两边都允许小概率错误的双侧测试。还要保持成员端的单侧接受或正确组合两侧错误。放大只改变错误参数，不会消除交互限制、适应性或 member/far gap。

放大同样出现在PCP 定理理路PCP 定理PCP theorem每个 NP 语言都具有多项式长度、对数随机性、常数查询且带常数可靠性间隙的概率可检验证明。的参数调整中，但不能只把“重复”当成免费操作：证明 oracle 必须在随机选择前固定，重复验证还会增加随机位和查询次数。交互协议的并行重复也可能需要专门定理；只有能建立各轮独立性理路独立性Statistical independence从概率表理解独立性，区分两两、相互和条件独立，并用可计算反例澄清零协方差与条件均值的限度。或足够弱相关性时，上述 Bernoulli 分析才可直接套用。

Boosting理路弱到强 Boosting 归约boosting reduction · weak-to-strong learning通过改变样本分布聚焦当前难点，把略优于随机的弱学习器归约为任意精度强学习器。虽然也把弱保证变强，却不是对同一学习器独立运行后取普通多数。它每轮根据此前错误重加权训练样本，让下一个弱分类器面对不同分布，再以加权投票组合；其训练误差下降依赖势函数和弱优势，而不是本页的 IID Bernoulli 重复。