algorithm - 随机算法

Question

我遇到了一个随机问题。:)

A，一种随机算法，确定输入 x 是否为素数。

该算法的工作方式如下：

1- 如果 x 是素数，则 A 输出 YES

2- 如果 x 不是素数，则 A 以 3/4 的概率输出 NO。

如果我们想让算法 A 以至少 1- (1/k) 的概率输出 NO，我们至少应该运行 A 多少次？

注意：一个“否”的答案意味着给定的输入 x 不是素数。

任何想法？

Answer 1

如果一个数字x不是素数，则n在算法的重复中产生“是”的概率是(1/4)^n = 4^(-n) = 2^(-2n)。

所以，如果你想达到1-(1/k)，你实际上是在寻找概率最多为 的False Positive1/k，从上面我们想要：

2^(-2n) <= 1/k   //log_2 on both sides:
-2n <= log(1/k) = log(1)-log(k) = 0 - log(k)
2n >= log(k)
n >= log(k)/2

因此，您要选择n可能的最小整数n >= log(k)/2，以保证True Negative的概率为1-1/k。

（注：log()均以 2 为底）。

示例：
如果您希望 99% 的时间都是正确的，那么您实际上是在寻找1-1/k=0.99, so1/k=1/100和k=100。

现在，根据上面的公式，请注意log_2(100) ~= 6.64，因此最小n的n >= log_2(100)/2是n==4。
意思是，您需要将算法重复 4 次才能达到 99%。

让我们检查一下这是否正确：

1. 首先检查概率确实大于 99%: 1-(1/4)^4 = 1-(1/256) ~= 0.996 >= 0.99，所以概率没问题。
2. 检查对于较小的整数（n==3），我们得到的正确率会低于 99%：1-(1/4)^3 = 1-1/64 ~= 0.984 < 0.99- 所以我们会失败n==3.