Two ways to use randomness
Randomized algorithms split into two families based on what the coin flips affect: the running time or the correctness.
Las Vegas algorithms
A Las Vegas algorithm always returns the correct answer, but its running time varies with the random choices. Randomized quicksort is a classic example: the output is always sorted, and randomness only influences how fast it finishes.
- Answer is always right.
- Time is a random variable.
Monte Carlo algorithms
A Monte Carlo algorithm has a bounded running time but may return a wrong answer with small probability. Primality tests that occasionally misjudge a number are typical.
- Time is bounded.
- Answer is probably right.
To shrink the error, you repeat a Monte Carlo algorithm with fresh randomness and combine the outcomes, driving the failure probability down rapidly.
Converting between them
A Monte Carlo algorithm whose answers can be checked can be turned into a Las Vegas one: rerun until the verified answer is correct. Going the other way, you can cut off a Las Vegas run early to bound its time at the cost of possible failure.
Key idea
Las Vegas algorithms always answer correctly with random running time, while Monte Carlo algorithms run in bounded time but may err, and repeating or verifying lets you convert between the two trade offs.