Problem:
Suppose that a randomized algorithm succeeds (e.g., correctly computes the minimum cut of a graph) with probability $ p $ (with $ 0 < p < 1$ ). Let $ \epsilon $ 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 - \epsilon $, at least one trial succeeds?
Solution:
Suppose we run the algorithm for $ n $ times and therefore the probability for all of these independent trials to fail is $ (1 - p)^n $.
The probability to success is therefore $ 1 - (1 - p)^n > 1 -\epsilon $.
$ \begin{eqnarray*} 1 - (1 - p)^n &>& 1 -\epsilon \\ - (1 - p)^n &>& -\epsilon \\ (1 - p)^n &<& \epsilon \\ \log((1 - p)^n) &<& \log \epsilon \\ n\log(1 - p) &<& \log \epsilon \\ n &>& \frac{\log \epsilon}{\log(1 - p)} \end{eqnarray*} $
Note the change of inequality sign in the last line, this is because $ \log(1 - p) < 0 $
Suppose that a randomized algorithm succeeds (e.g., correctly computes the minimum cut of a graph) with probability $ p $ (with $ 0 < p < 1$ ). Let $ \epsilon $ 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 - \epsilon $, at least one trial succeeds?
Solution:
Suppose we run the algorithm for $ n $ times and therefore the probability for all of these independent trials to fail is $ (1 - p)^n $.
The probability to success is therefore $ 1 - (1 - p)^n > 1 -\epsilon $.
$ \begin{eqnarray*} 1 - (1 - p)^n &>& 1 -\epsilon \\ - (1 - p)^n &>& -\epsilon \\ (1 - p)^n &<& \epsilon \\ \log((1 - p)^n) &<& \log \epsilon \\ n\log(1 - p) &<& \log \epsilon \\ n &>& \frac{\log \epsilon}{\log(1 - p)} \end{eqnarray*} $
Note the change of inequality sign in the last line, this is because $ \log(1 - p) < 0 $
No comments:
Post a Comment