Las Vegas vs Monte Carlo Algorithms

Core Idea

Randomized algorithms split into two fundamental classes based on where the randomness manifests. Las Vegas algorithms always produce the correct answer but have random running time — randomized quicksort always sorts correctly, but the number of comparisons varies. Monte Carlo algorithms run in deterministic (or bounded) time but may produce incorrect results with bounded probability — the Miller-Rabin primality test runs in fixed polynomial time but has a small false-positive probability. The distinction matters for complexity theory (ZPP vs BPP/RP) and for practice: Las Vegas algorithms compose trivially (correctness is guaranteed) while Monte Carlo algorithms require careful error management when chained together.

Explainer

From your study of randomized algorithms, you understand that coin flips can improve algorithmic performance. The Las Vegas / Monte Carlo classification sharpens this into a precise tradeoff between two desirable properties: guaranteed correctness and guaranteed running time. Every randomized algorithm sacrifices one of these — you cannot have both with nontrivial randomization (or you would have a deterministic algorithm).

Las Vegas algorithms sacrifice predictable running time for guaranteed correctness. Randomized quicksort always produces a correctly sorted array, but the number of comparisons is a random variable with expectation O(n log n). The worst-case time is still O(n^2) — it is just exponentially unlikely. Randomized algorithms for finding medians, hashing, and computational geometry often fall in this class. The complexity class ZPP captures Las Vegas polynomial-time computation: problems solvable with zero error and expected polynomial running time.

Monte Carlo algorithms sacrifice guaranteed correctness for predictable running time. The Miller-Rabin primality test runs in fixed polynomial time but may declare a composite number prime with probability at most 1/4 per trial. Repeating k times drives the error to (1/4)^k — for k = 40, the error probability is below 2^(-80), far smaller than hardware failure rates. The complexity classes RP (one-sided error) and BPP (two-sided error) capture different flavors of Monte Carlo computation. A crucial subtlety: one-sided error is more powerful for amplification because you know which direction might be wrong.

The distinction becomes operationally important when randomized subroutines are composed. A Las Vegas call inside a loop contributes variable running time but no error accumulation — you can call it a million times and the output is still correct. A Monte Carlo call inside a loop accumulates error: m calls each with error epsilon give overall error up to m * epsilon by the union bound. Managing this requires amplifying each call's success probability, which costs O(log(m)) factor per call. This compositional difference is why Las Vegas algorithms are preferred when available, and why the question of whether RP = ZPP (can every one-sided Monte Carlo algorithm be made Las Vegas?) remains a fundamental open question in complexity theory.