Las Vegas algorithm

A Las Vegas algorithm guarantees correctness on every execution, but its execution time can vary because it makes random choices. The standard formulation is therefore a pair of guarantees: certain output correctness and a probabilistic bound on running time, commonly expressed as expected or high-probability complexity.

The distinction from Monte Carlo algorithms concerns which quantity is allowed to fail. A Monte Carlo method runs within a prescribed or bounded time and can have a small probability of error; a Las Vegas method may take longer, but it does not knowingly return a wrong answer. A Las Vegas algorithm can sometimes be obtained by repeating a randomized procedure until a verifiable success condition is met.

A Las Vegas algorithm combines randomization with a certificate, test, or invariant that identifies whether a tentative computation is valid. If the test fails, the algorithm retries or changes course; if it succeeds, the returned result is correct by construction. The random choices are thus a performance device rather than a source of accepted error.

Randomized quicksort illustrates the principle when its partitioning is arranged so that the algorithm always sorts correctly, while a random pivot makes highly unbalanced partitions unlikely. Its expected running time is quadratic only in the worst sequence of choices, and is typically O(n log n) under standard random-pivot analysis. Similar reasoning applies to randomized data structures, where random priorities or levels influence height and update cost without changing the abstract operations' correctness.

Las Vegas methods are valuable when an incorrect answer is unacceptable and a result can be checked efficiently. They appear in sorting, search, computational geometry, data structures, symbolic computation, and some exact optimization procedures. A classic example is Karger's randomized contraction method for finding a graph's minimum cut: a single trial can fail to find the minimum cut, but a candidate cut can be verified, and repeated trials raise the probability of finding the optimum; the resulting repeat-until-certified formulation is Las Vegas in settings where verification and restart are explicit.

Analysts commonly use expectation, tail bounds, and amortized reasoning. Independence assumptions about the random number generator, the cost of restarting, and the distinction between expected time and worst-case time all matter. An expected bound does not promise that every individual run is fast, so production systems may impose time limits or use additional probability bounds.

The phrase “Las Vegas” describes a correctness–performance trade-off, not a particular programming language, hardware platform, or source of randomness. Implementations may use pseudorandom generators rather than physical randomness, provided their statistical or adversarial requirements are appropriate. Weak randomness can undermine performance assumptions even when the algorithm remains logically correct.

Restarting is not automatically harmless: a rare but very long execution can dominate expected cost, and repeated trials may require careful scheduling. In adversarial settings, an attacker who can predict or influence random choices may force poor behavior; randomized algorithms are therefore studied alongside cryptography and adversarial analysis. Conversely, a Las Vegas design can be preferable to a Monte Carlo design in exact computation, because an independently checkable certificate converts uncertainty about duration into certainty about the answer.

Las Vegas algorithm

A randomized algorithm that always produces a correct result, with randomness affecting running time or resource consumption.

Monte Carlo algorithm

A randomized algorithm with a bounded or controlled running time that may produce an incorrect result with limited probability.

Expected running time

The average running time calculated over the algorithm's random choices, usually for a fixed input.

Certificate

A checkable object or condition that demonstrates that a computed result is valid.