Randomized Algorithms

Randomized algorithms make random choices during execution to gain efficiency, simplicity, or robustness, with performance and correctness expressed as probabilistic guarantees rather than worst-case certainties.

Definition

A randomized algorithm is an algorithm that uses a source of random bits to make some of its decisions, so that its running time, output, or both are random variables analyzed by their expectation or probability distribution.

Scope

This topic covers algorithms that use randomness as a computational resource: the Las Vegas model (always correct, randomized running time) and the Monte Carlo model (fixed running time, bounded error probability), canonical examples such as randomized quicksort, randomized selection, primality testing, and randomized data structures like skip lists, and the probabilistic analysis tools (expectation, variance, tail and concentration inequalities) used to reason about them.

Core questions

• How can introducing randomness make an algorithm faster or simpler than any known deterministic one?
• What is the distinction between Las Vegas and Monte Carlo algorithms?
• How is expected running time or error probability analyzed?
• How do concentration inequalities bound the chance of bad outcomes?
• How can the error of a Monte Carlo algorithm be reduced by repetition?

Key concepts

• random bits as a resource
• Las Vegas algorithm
• Monte Carlo algorithm
• expected running time
• error probability and amplification
• concentration inequalities
• randomized quicksort
• skip lists

Key theories

Las Vegas versus Monte Carlo

Las Vegas algorithms always produce a correct result but have randomized (analyzed in expectation) running time, while Monte Carlo algorithms run within a fixed time but may produce an incorrect result with bounded probability, which repetition can shrink.

Probabilistic primality testing

Randomized tests such as Miller-Rabin certify primality with high confidence in polynomial time by checking random witnesses; a composite number is exposed by most witnesses, so repeated trials make the error probability negligible.

Clinical relevance

Randomized algorithms are widely deployed: Miller-Rabin primality testing underpins public-key cryptography, randomized hashing and load balancing keep distributed systems efficient, randomized quicksort and quickselect give robust expected performance, and randomized sampling and sketching enable processing of massive data streams.

History

Probabilistic algorithms rose to prominence in the 1970s with the Solovay-Strassen and Miller-Rabin primality tests, which made randomness a respectable computational tool. The 1980s and 1990s saw randomized data structures (skip lists, treaps), randomized graph and geometric algorithms, and the systematic theory codified in Motwani and Raghavan's 1995 textbook.

Key figures

• Michael Rabin
• Robert Solovay
• Volker Strassen
• Rajeev Motwani
• Prabhakar Raghavan

Seminal works

• motwani1995
• rabin1980
• cormen2009

Frequently asked questions

How can a Monte Carlo algorithm be trusted if it can be wrong?

Its error probability is bounded and known, and for one-sided-error algorithms it can be made arbitrarily small by running the algorithm several times with independent randomness. After enough repetitions the chance of a wrong answer is far smaller than the chance of a hardware failure.

Why is randomized quicksort preferred over deterministic quicksort?

Deterministic quicksort can hit its O(n squared) worst case on adversarial or already-sorted input due to poor pivot choices. Randomly choosing pivots makes that worst case extremely unlikely regardless of input, giving expected O(n log n) performance on every input.