概率放大

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

单次正确率 $2/3$ 时，重复 $O(\log n)$ 次可把长度 $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、RP 等类的具体常数阈值不重要，只要与 $1/2$ 保持常数间隔即可。Chernoff 方法公理库Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds对随机变量施加指数变换并优化参数，以获得指数级尾概率上界。解释双边多数票的指数衰减；单侧错误则由独立事件概率直接相乘。它让BPP公理库复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。、RP公理库复杂度类 RPComplexity class RP具有单边误差多项式时间随机算法的语言类。等定义中的常数具有鲁棒性，也能在多项式次 union bound 前把单次失败压到逆多项式或可忽略水平。

在亚线性模型中，重复的代价必须记回原资源。随机通信协议公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。重复 $r$ 次通常把通信量乘 $r$，并行执行还需单独报告轮数；随机查询算法公理库确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity在坐标访问模型中分别定义确定性、零误差随机和有界误差随机查询复杂度，并固定最坏与期望口径。会增加查询次数，复用相同随机查询则未必独立；性质测试器公理库单侧与双侧性质测试器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 重复。