How can we get a Las Vegas algorithm from a Monte Carlo one?

Question

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?

Answer 1

First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is zero.

So, the algorithm should be as following:

Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

Also, verify the solution from MC(n) by the given in the question which takes t(n) running time; because you don't know that monte carlo algorithm outputs correct or not. Also I removed the else condition, I don't see it is important here. So, the algorithm should be edited as following:

Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     answer_from_verifier = output_Verify(solMC)
3)     if answer_from_verifier is correct
4)         return solMC
7)     end
8) end

---

Now, the expected running time is:

$E[X]= \sum_{i=0}^{\infty} (1-\gamma)^i \gamma (i+1) (T(n)+t(n)) $

$= \gamma (T(n) + t(n)) \sum_{i=0}^{\infty} (1-\gamma)^i (i+1)$

$= \gamma (T(n) + t(n)) . 1/\gamma^2$

$= \frac{T(n)+t(n)}{\gamma} $