I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills.
Here is the exercise:
Exercise 1.3: Consider a Monte Carlo algorithm $A$ for a problem $\Pi$ whose expected running time $T(n)$ on any instance of size $n$ and that produces a correct solution with probability $\gamma(n)$. Suppose further that given a solution to $\Pi$, we can verify its correctness in time $t(n)$. Show how to obtain a Las Vegas algorithm that always gives a correct answer to $\Pi$ and runs in time at most $(T(n)+t(n))/\gamma(n)$.
My attempt to solve this exercise is:
Algorithm LA
1) for i = 1 to 1/gamma(n) do
2) solMC = MC(n)
3) if solMC is correct
4) return solMC
5) else
6) solMC = MC(n)
7) end
8) end
The idea of my Las Vegas algorithm LV was to re-run the Monte Carlo algorithm, MC
in my code, some iterations until the correct answer is given.
I found that $\Pr[MC(n) \text{ is called at iteration } i]=(1-\gamma(n))^i$. So I choose the iterations from 1
to 1/gamma(n)
. In this case, $\Pr[MC(n) \text{ is called at iteration } i]=(1-\gamma(n))^{1/\gamma(n)}$ which goes either to $0$ or $1/e$ as $\gamma(n)$ goes to either $1$ or to $0$, respectively. I think this does not answer the question.
How would you solve this problem?