algorithm - 随机算法的属性(蒙特卡罗，拉斯维加斯)

Question

我现在正在学习拉斯维加斯和蒙特卡洛算法自己，有两个问题可能很简单但我无法回答，如果有人能帮助我......提前谢谢

1. 考虑针对问题 P 的蒙特卡洛算法 A，其预期运行时间在任何大小为 n 的实例上至多为 T(n)，并以 y(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。