我错过了关于随机算法的讲座，无法放大双侧误差算法的概率。
有人可以解释为什么以下算法通过重复给出正确输出的概率增加以及如何计算该概率吗？
L 是一种形式语言
如果输入 x ∈ L，则算法的输出将为 YES，概率为 2/3
如果输入 x ！∈ L，则算法的输出将为 NO，概率> 1/2
提前谢谢你
你需要一个时髦的决策规则来破解这个规则。运行算法 n 次，如果输出的至少 7/12(= 介于 1/2 和 2/3 之间(的比例为 YES，则输出为 YES。
挥手的理由是，对于每个NO输入，YES输出的预期分数根据大数定律收敛到最多1/2，对于每个YES输入，YES输出的预期分数收敛到至少2/3。形式上，我们必须调用霍夫丁不等式或等价的东西，这表明对于某些固定常数c，误差概率随O(exp(-cn))而降低。