Las Vegas algorithm: randomized methods that guarantee correctness

Key characteristics

• Correctness: The algorithm always returns a correct result or a failure notice; it does not return an incorrect solution.
• Randomized performance: Running time, number of iterations, or resource consumption are random variables; analyses usually give expected time or tail bounds.
• Verification: Many Las Vegas methods incorporate an internal check that verifies a candidate result, allowing rejection and retry when the check fails.
• Practical trade-offs: They often simplify implementation and improve expected performance while preserving exactness.

Examples and common uses

Classic examples include randomized QuickSort or QuickSelect when the pivot is chosen uniformly at random; these versions are Las Vegas because the sorted output is always correct while the running time is an expected value (typically O(n log n) for QuickSort). Other examples are randomized algorithms for geometric problems, certain hashing-based data structures that rehash on collisions, and incremental randomized algorithms for low-dimensional linear programming.

Developers and researchers may prefer Las Vegas algorithms when exactness is required but improved average performance or simpler code is desirable. For accessible introductions and surveys see randomized algorithms overview and algorithm textbooks referenced at randomness in computing.

History and terminology

The names "Las Vegas" and "Monte Carlo" are metaphors referring to gambling and probability. The distinction is older than any single publication: authors adopted the labels to emphasize whether randomness affects correctness or only efficiency. Formal treatments of randomized algorithms and the Las Vegas/Mont e Carlo distinction appear in algorithm and complexity literature; for further technical reading see sources on Monte Carlo vs Las Vegas and surveys at randomized methods.

Analysis, conversions, and noteworthy facts

Las Vegas algorithms are analyzed in terms of expected running time and probability tail bounds (how unlikely it is to exceed a large cost). In some cases a Monte Carlo algorithm can be turned into a Las Vegas algorithm by adding a fast verification step: run the Monte Carlo procedure and then check its output deterministically; if the check fails, repeat or switch to a fallback deterministic method. This conversion is a common technique when verification is cheap relative to recomputation; see verification strategies.

Researchers also study derandomization: replacing randomness with deterministic choices while preserving performance guarantees. For practical code and examples of randomized QuickSort and selection methods consult implementation notes and tutorials at practical randomized algorithms.