2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Why do you think this does not answer the question? Can you spell it out more precisely, and specifically what requirement you think it doesn't solve? What other fixes or approaches have you considered? Have you considered changing the number of iterations? Hint: How do we measure/evaluate the running time of a Las Vegas algorithm? $\endgroup$ – D.W. Mar 11 '16 at 4:09
  • $\begingroup$ Hint: some definitions of Las Vegas allows you do output "I don't know". $\endgroup$ – Raphael Mar 11 '16 at 7:14
  • $\begingroup$ @Dr W I think it does not solve the question because Las Vegas algorithm must give the correct answer with probability $1$. However my attempt only gives me the correct answer with probability less than $1/e$ (I think). $\endgroup$ – drzbir Mar 11 '16 at 17:32
  • $\begingroup$ @Raphael I am using the definition of the book "randomized algorithms" by Rajeev Motwani and Prabhakar Raghavan. They defined a Las Vegas algorithm as an algorithm that always gives the correct answer. In other words, a Las Vegas algorithm is a Monte Carlo algorithm with error probability $0$. $\endgroup$ – drzbir Mar 11 '16 at 21:52
  • $\begingroup$ That's still possible. Hint: it only terminates with probability 1. $\endgroup$ – Raphael Mar 11 '16 at 22:44
2
$\begingroup$

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} $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.