Algorithms: Design and Analysis, Part 1 - Exam Question 13

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$