我刚刚完成了coursera中algo专业化课程的第一个模块。
有一道考试题我不太明白我通过了那次考试，所以我没有必要重考。
出于好奇，我想学习这个问题的原则。
问题是这样发布的：
假设随机算法成功（例如，正确计算
图的最小割）概率为p（0是一个小的正数（小于1）。
你需要多少次独立运行算法来确保
那么，至少有一次试验成功的概率是1-ϵ？
给出的选项有：
对数（1-p）/logϵ
对数（P）/对数_
对数（p）
对数（1-p）
我试了两次都错了我的尝试是：
对数（1-p）/log_
对数（1-p）
我不太想知道正确的答案。我想学习这个问题背后的原理和它的要求。所以我知道以后怎么回答类似的问题。
我已经把这个贴在论坛上了，但是一个月后没有人回复。所以我在这里尝试。
不需要直接发布答案如果你让我进入“啊哈”时刻，我会把它标为正确的。
谢谢。
最佳答案
你需要多少次独立运行该算法，以确保至少有一次试验成功（概率至少为1-ϵ）？
让我们换个说法：
独立试验的最小数量是多少，以至于所有试验失败的概率小于或等于ϵ？
根据independent events的定义，所有这些事件发生的概率都是它们各自概率的乘积。由于一次试验失败的概率是(1-p)，因此n试验失败的概率是(1-p)^n。
这给了我们一个关于n的不等式：
(1-p)^n <= ϵ
关于algorithm - 独立的时间以确保图形的最小切割至少一次试验成功，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45873859/