蒙特卡罗算法什么时候解决问题？

Question

我们什么时候可以说蒙特卡罗算法解决了一个问题？

以维基百科关于monte carlo algorithms

例如，Solovay-Strassen Pruality测试用于确定给定数量是否是素数。它总是回答素数输入;对于复合输入，它概率至少½和真，概率小于½。

如果Solovay-strassen测试只能为1％的复合输入答案，则会发生什么？

我们仍然会说它解决了测试原始问题吗？

或者有一些要求，类似于Monte Carlo算法必须以超过一半的情况来回答真实情况？

Answer 1

蒙特卡洛一般来说，用于解决各种不同类型的问题。在这种特殊情况下，您想要了解如果随机变量是常量1，则为学习。这个想法很简单，对随机变量进行多次进行样本，（每个样本独立于先前的样本以避免偏见）并检查所有结果是否为1.如果至少一些结果为0，则我们知道无需随机变量不是常数1（在索洛韦 - 划分测试上下文中，数字是复合材料）。

重要的是要强调，因为蒙特卡罗是一种随机算法，所以如果据说返回错误答案的概率低于一些阈值（我们将调用 $ \ epsilon $ ）。

如果所有结果为1？有可能是恒定的1，但也有一个可能的机会，我们没有幸运的是，当它们也可以是0时，所有结果都是0.如果采样1的概率为 $ p <1 $ ，然后在 $ n $ 样本中获取所有1的概率是 $ p_n= p ^ n $ 。请注意，虽然 $ n $ 增加 $ p_n \ lightarrow 0 $ 。我们可以指定一个阈值，假设 $ \ epsilon= 10 ^ { - 10} $ ，使得如果 $ p_n < \ epsilon $ （即具有假阳性的概率小于 $ \ epsilon $ ）我们对该结果确定。

---

现在回答你的问题。 $ \ forall p <1，\ epsilon> 0 \ space \存在n \ space p ^ n <\ epsilon $ 。这是什么告诉你的？

无论成功概率如何，就小于 $ 1 $ （例如 $ p= 0.99 $ 或 $ p= 0.01 $ 或 $ p= 0.5 $ ）和阈值 $ \ epsilon $ 存在 $ n $ ，这样如果我们运行实验 $ n $ 时间（Sample $ n $ times，随机变量独立），我们将在大多数 $ \ epsilon $ 。所以Monte Carlo可以应用于 $ p $ 的非退化值，只有数字 $ n $ 必须调整样本以满足 $ \ epsilon $ 阈值要求。