Let's say that I have a Las Vegas algorithm for a given problem (whose answer is
false for simplicity) with a chance of answering
p, and a Montecarlo algorithm for the same problem which is
q-correct (it gives the correct answer with a probability of at least
Could there be any way to combine them both in order to improve the overall chance of finding the correct answer? This could be running them in turns, or repeating any given algorithm for
k times and then the other one
SO far, I thought of doing the following:
- Call the Las Vegas algorithm
- If it hasn't given an answer, run the MonteCarlo algorithm
k'times so that, at least, the chance of the given answer being wrong is less than the chance the Las Vegas algorithm has for not answering at all
Could there be any other way to improve the success chance?
I have tried finding any case where this has been done, but apart from converting one kind of algorithm into the other, I haven't found much.