随机算法的性质（蒙特卡洛，拉斯维加斯）

Question

我现在正在学习拉斯维加斯和蒙特卡罗算法，并有两个问题可能很简单，但我无法回答他们，如果有人可以帮助我......谢谢预先

1. 考虑蒙特卡洛算法为一个问题P上产生的概率Y（N）正确的溶液大小为n的任何实例，其预期的运行时间为至多T（n）中。进一步假设给出了P的一个解，我们可以验证它在时间t（n）中的正确性。演示如何获得拉斯维加斯算法，该算法始终给出P的正确答案，并且最多在预期时间内运行（T（n）+ t（n））/ y（n）。

2. 让0 <ε2<ε1< 1.考虑蒙特卡罗算法给出正确的解决方案的一个问题的概率至少1-ε1，而不管输入的。无论输入如何，该算法独立执行多少次都足以提高获得至少为1-ε2的正确解的概率？

Answer 1

1. 只是重复运行你的算法和测试结果，直到你得到一个正确的答案。每次运行和检查需要（T（n）+ t（n））个时间单位，并且运行次数是平均值为1/y（n）的几何随机变量。

2. 一次运行失败的概率是多少？两次运行？ n运行？设n次运行失败的概率等于e2并求解n。