In textbook "Randomized Algorithm" by Motwani and Raghavan,
Exercise 1.4: Let $0 < \epsilon_2 < \epsilon_1 < 1$. Consider a Monte Carlo algorithm that gives the correct solution to a problem with probability at least $1-\epsilon_1$, regardless of the input. How many independent executions of this algorithm suffice to raise the probability of obtaining a correct solution to at least $1-\epsilon_2$, regardless of the input?
if we have $0 < \epsilon_2 < \epsilon_1 < 1$, then if follows that $ 0 < 1- \epsilon_1 < 1 - \epsilon_2 < 0$. we want to find how many executions of the algorithm to raise the bound from $1-\epsilon_1$ to $1 - \epsilon_2$, we only care about how many times of $\epsilon_1$ to make it less than $\epsilon_2$ as follows:
$$0 < \epsilon_1 * \epsilon_1 * ... *\epsilon_1 < \epsilon_2 < \epsilon_1 < 1$$
$\epsilon_1 * \epsilon_1 * ... *\epsilon_1$ could be written as $\epsilon_1^{x}$. So, we have the following equality: $\epsilon_1^{x} < \epsilon_2$ Take the log of base 2. we get: $$\log_2\epsilon_1^x < log_2\epsilon_2$$ equals: $$x\log_2\epsilon_1 < \log_2\epsilon_2$$ equals $$x < \frac{log_2\epsilon_2}{\log_2\epsilon_1}$$
But, if you take $\epsilon_1=1/2$ and $\epsilon_2=1/4$ then x<2 and therefore x could be 1 or less, but this is not true for above equality. Can you tell me where is wrong in my proof?
Thank you
Since $0 < \epsilon_1 < 1$, $\log_2 \epsilon_1$ is negative. Thus we get $x > \dfrac{\log_2 \epsilon_2}{\log_2 \epsilon_1}$ from $x\log_2 \epsilon_1 < \log_2 \epsilon_2$, not $x < \dfrac{\log_2 \epsilon_2}{\log_2 \epsilon_1}$.