Classfication of randomized algorithms

Question

From Wikipedia about randomized algorithms

One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time, and probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo algorithms) or fail to produce a result (Las Vegas algorithms) either by signalling a failure or failing to terminate.

1. I was wondering how the first kind of "algorithms use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time?
2. What differences are between it and Las Vegas algorithms which may fail to produce a result?
3. If I understand correctly, probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just one kind of randomized algorithms, and the other kind is those use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time?

Answer 1

1. An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.

2. This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.

3. These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.

There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.

Answer 2

The two terms randomized algorithms and probabilistic algorithms are used in two different contexts. Randomized algorithms are algorithms that use randomness, in contradistinction with deterministic algorithms that do not. Probabilistic algorithms, for example probabilistic algorithms for primality testing, are algorithms that use randomness and could make an error with some (hopefully) small probability.

An important distinction has to be made between Monte Carlo algorithms and Las Vegas algorithms. Las Vegas algorithms are randomized algorithms that always return the correct answer, but their running time depends on the coin tosses. An example is integer factoring algorithms – they always return the correct factors, but their running time depends on the randomness. When stating the running time of a Las Vegas algorithm (say a factoring algorithm), we actually state the expected running time; if we are unlucky, the algorithm could run for longer.

Monte Carlo algorithms, on the other hand, are randomized algorithm whose running time is set ahead of time. Such algorithms can make a mistake, but usually the error probability is very low. A good example is probabilistic primality testing. These algorithms are very fast but could make an error. However, the error probability is slow low that in practice, they never make a mistake.

Every Las Vegas algorithm can be converted to a Monte Carlo algorithm by stopping execution after a long enough time, so Las Vegas algorithms are in some sense "better" than Monte Carlo algorithms.