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

Question

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

1. 考虑问题 P 的蒙特卡洛算法 A，该问题 P 的预期运行时间在任何大小为 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。