独立的时间以确保图的最小切割至少一次试验成功
independent times to ensure minimum cut of graph at least one trial succeeds
我刚刚完成了 coursera 中算法专业课程的第一个模块。
有道题我不是很明白。我已经通过了那个考试，所以我没有必要重考。
出于好奇，想了解一下这个问题的原理。
问题是 post 编辑的：
Suppose that a randomized algorithm succeeds (e.g., correctly computes
the minimum cut of a graph) with probability p (with 0 < p < 1). Let ϵ
be a small positive number (less than 1).
How many independent times do you need to run the algorithm to ensure
that, with probability at least 1−ϵ, at least one trial succeeds?
给出的选项是：
log(1−p)/logϵ
log(p)/logϵ
logϵ/log(p)
logϵ/log(1−p)
我试了两次，都错了。我的尝试是：
- log(1−p)/logϵ
- logϵ/log(1−p)
我不是很想知道正确答案。我想了解这个问题背后的原则以及它的要求。以便我以后知道如何回答类似的问题。
我已经 post 在论坛上编辑了这个，但是一个月后没有人回复。所以我在这里尝试一下。
无需 post 直接回答。如果你让我明白了，我会把它标记为正确的。
谢谢。
How many independent times do you need to run the algorithm to ensure that, with probability at least 1−ϵ, at least one trial succeeds?
让我们改写一下：
What is the smallest number of independent trials such that the probability of all of them failing is less than or equal to ϵ?
根据 independent events 的定义，它们全部发生的概率是它们各自概率的乘积。由于一次试验失败的概率为 (1-p)，因此 n 次试验失败的概率为 (1-p)^n。
这给出了 n 的不等式：
(1-p)^n <= ϵ
我刚刚完成了 coursera 中算法专业课程的第一个模块。
有道题我不是很明白。我已经通过了那个考试，所以我没有必要重考。
出于好奇，想了解一下这个问题的原理。
问题是 post 编辑的：
Suppose that a randomized algorithm succeeds (e.g., correctly computes the minimum cut of a graph) with probability p (with 0 < p < 1). Let ϵ be a small positive number (less than 1).
How many independent times do you need to run the algorithm to ensure that, with probability at least 1−ϵ, at least one trial succeeds?
给出的选项是：
log(1−p)/logϵ
log(p)/logϵ
logϵ/log(p)
logϵ/log(1−p)
我试了两次，都错了。我的尝试是：
- log(1−p)/logϵ
- logϵ/log(1−p)
我不是很想知道正确答案。我想了解这个问题背后的原则以及它的要求。以便我以后知道如何回答类似的问题。
我已经 post 在论坛上编辑了这个，但是一个月后没有人回复。所以我在这里尝试一下。
无需 post 直接回答。如果你让我明白了，我会把它标记为正确的。
谢谢。
How many independent times do you need to run the algorithm to ensure that, with probability at least 1−ϵ, at least one trial succeeds?
让我们改写一下：
What is the smallest number of independent trials such that the probability of all of them failing is less than or equal to ϵ?
根据 independent events 的定义，它们全部发生的概率是它们各自概率的乘积。由于一次试验失败的概率为 (1-p)，因此 n 次试验失败的概率为 (1-p)^n。
这给出了 n 的不等式：
(1-p)^n <= ϵ