retagged by
234 views
5 votes
5 votes

Suppose that a randomized algorithm succeeds with probability $p$  (with $0<p<1).$  Let $n$ be independent trials we need to run the algorithm to ensure that, with probability at least $1-\epsilon$, at least one trial succeeds.
Which of the following relation must hold true?

  1. $(1-p)^{n} \leq \epsilon$
  2. $1-p^{n} \leq \epsilon$
  3. $p^{n} \leq \epsilon$
  4. $p^{n} \leq \epsilon$
retagged by

1 Answer

9 votes
9 votes
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:
$$
\begin{aligned}
1-(1-p)^{n} & \geq 1-\epsilon \\
(1-p)^{n} & \leq \epsilon \text { (flipping inequality due to change in sign) }
\end{aligned}
$$
Answer:

Related questions