我错过了随机算法的讲座，不能换我的头周围放大双面误差算法的概率。
有人能解释为何以及如何可以在概率计算，下面的算法给出通过重复正确的输出增加的概率是多少？
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。在形式上，我们必须调用Hoeffding's inequality或等价的东西，这表明错误的概率为O(exp(-cn))降低了一些固定不变c。