Randomized Algorithms

A randomized algorithm is a procedure that flips coins as it runs.

17 frameworks, from 1946 to today · Algorithms · Computer Science

still a working view ended · each leads to its entry below

Overview

A randomized algorithm is a procedure that flips coins as it runs1. The coins are not a confession of weakness: they are a tool. Sometimes randomness buys speed, sometimes simplicity, sometimes a guarantee that no deterministic method is known to give. The field's central question is how far that tool reaches—which problems become easier when an algorithm is allowed to guess, and what it costs in certainty when it does.

The bargain is always the same. A deterministic algorithm promises a correct answer on every input. A randomized one promises a correct answer with high probability, or a correct answer on average, or an answer whose error can be driven arbitrarily low by repetition1. What practitioners discovered over the twentieth century is that this bargain is often spectacularly good: randomness can turn an intractable computation into a routine one, and a complicated one into a short one.

Gambling and sampling before computers

Probability entered computation through physics and statistics. The Monte Carlo method—named for the casino, by Stanislaw Ulam and John von Neumann in the 1940s—estimated quantities too hard to compute directly by simulating random samples. Ulam's first inspiration, around 1946, was counting the possible outcomes of solitaire hands; the method matured at Los Alamos, where neutron diffusion problems were solved by sampling particle histories rather than solving the transport equations2. The idea was old in spirit—Buffon's needle, an eighteenth-century geometric-probability experiment, estimates π by dropping needles on a lined floor—but the computer made it a general technique.

The same decade produced the first algorithmic coin-flip with a proof. In 1947, working on primality testing, the number theorist Derrick Henry Lehmer used a randomized test; and in the 1970s the idea crystallized. In 1976, Gary Miller gave a deterministic test for primality conditional on the unproven Extended Riemann Hypothesis3. Michael Rabin, in 1976–77, and Robert Solovay and Volker Strassen, in 1977, turned the same mathematics into unconditional randomized tests: pick random witnesses, and if the number passes, it is prime with high probability. Here was the template for everything after—a fast test that can err, whose error shrinks exponentially with repetition.

Fingerprinting and the algebra of verification

In 1977, Richard Karp and Richard Lipton introduced randomized fingerprinting: to test whether two large objects are equal, evaluate a compact random hash of each and compare. The same year, Robert Freivalds showed that matrix multiplication can be checked in time proportional to reading the matrices—pick a random vector, multiply, compare—rather than recomputing the product. These results established a principle: verification can be cheaper than computation, if you allow a small chance of being fooled.

The principle deepened with universal hashing, introduced by J. Lawrence Carter and Mark Wegman in 19791. A family of hash functions is universal if any two distinct keys collide with probability at most 1/m over a random choice from the family. This gave hash tables provable expected performance against any input, not just random ones—a crucial shift, because it moved randomness from the data to the algorithm14. The same construction underlies later work on perfect hashing (Fredman, Komlós, and Szemerédi, 1984) and on streaming sketches.

Probabilistic complexity: giving randomness a name

By the late 1970s the field needed a vocabulary. In 1977, John Gill defined the class BPP—bounded-error probabilistic polynomial time—the problems solvable in polynomial time with error probability at most 1/3 (reducible to any ε by repetition). Related classes followed: RP (one-sided error, no false positives), ZPP (zero error, expected polynomial time), and PP (unbounded error). The open question that has organized the field ever since is whether randomness adds power at all: is BPP equal to P1? Most researchers believe it is, and the history of derandomization is the long campaign to prove it.

Derandomization and pseudorandomness

If randomness is to be eliminated, it must be replaced by something that looks random to the algorithm using it. The probabilistic method—pioneered by Paul Erdős in the 1940s and 1950s—had already shown that a random object with a desired property exists by proving the property holds with positive probability; the challenge was finding it15. In 1988, Raghu Meka and others aside, the decisive step came from the method of conditional expectations (Erdős and Selfridge, 1973) and its algorithmic form: the method of conditional probabilities, which turns an existence proof into a deterministic construction by fixing variables one at a time, always keeping the conditional expectation favorable.

The deeper engine was pseudorandom generators: deterministic procedures that stretch a short random seed into a long string indistinguishable from random by any efficient test. Building on work by Manuel Blum, Silvio Micali, and Andrew Yao in the early 1980s, Russell Impagliazzo and Avi Wigderson showed in 1997 that if certain problems are hard enough, then $BPP = P$—hardness and randomness are two sides of one coin. The Nisan–Wigderson generator (1994) made this concrete for space-bounded computation. Derandomization thus became a program of trading computational hardness for the elimination of chance.

Randomized rounding and the optimization toolkit

In the early 1990s, randomized algorithms entered combinatorial optimization through randomized rounding. The idea, developed by Prabhakar Raghavan and Clark Thompson around 1987 and named by Raghavan in 1988, is to solve a linear-programming relaxation, then round each fractional variable up or down at random with probability equal to its fractional value. The expected cost is exactly the LP optimum, and concentration inequalities (Chernoff bounds) show the result is close to optimal with high probability. This gave clean approximation algorithms for set cover, multicommodity flow, and scheduling, and it remains a standard technique alongside the deterministic LP-rounding and primal-dual methods.

Markov chains and counting

A different lineage runs through Markov chain Monte Carlo. The Metropolis algorithm (1953) and the Gibbs sampler (developed in statistical physics and imaging in the 1980s) sample from complicated distributions by simulating a Markov chain whose stationary distribution is the target67. In computer science the landmark was Jerrum, Valiant, and Vazirani's 1986 result that approximate counting and almost-uniform sampling are computationally equivalent. Then Mark Jerrum and Alistair Sinclair (1989) proved that the Markov chain for the Ising model mixes rapidly, and in 1993 Jerrum, Sinclair, and Vigoda gave a polynomial-time algorithm for the permanent—a problem whose exact computation is #P-hard. The technique—bounding the mixing time via conductance or coupling—became a field of its own, with applications to volume estimation, contingency tables, and statistical physics.

Incremental construction and geometric algorithms

In computational geometry, randomness simplified algorithms dramatically1. Randomized incremental construction, developed by Kenneth Clarkson and Peter Shor in 1989 and by Ketan Mulmuley, and analyzed by Raimund Seidel in 1991, builds a structure by inserting objects in random order; the expected cost is often linear even when the worst case is quadratic. Seidel's 1993 linear-programming algorithm for fixed dimension is the canonical example: it solves a linear program by processing constraints in random order, and the analysis shows the expected number of basis changes is bounded. The same paradigm underlies randomized algorithms for convex hulls, Delaunay triangulations, and smallest enclosing balls.

Streaming, sketching, and numerical linear algebra

As data grew, randomness became a way to compress. In 1981, Philippe Flajolet and G. Nigel Martin estimated the number of distinct elements in a stream using hashing and bit patterns—the ancestor of sketches. In 1985, Leslie Valiant introduced randomized numerical linear algebra in embryo with random sampling for matrix computations; the modern field, using random projections (the Johnson–Lindenstrauss lemma, 1984) to reduce dimension, took off in the 2000s with work by Petros Drineas, Michael Mahoney, and others on fast approximate matrix multiplication and least-squares regression. The count-min sketch (Cormode and Muthukrishnan, 2005) and HyperLogLog (Flajolet et al., 2007) made approximate counting and frequency estimation routine in databases and networks.

Interactive proofs and the power of randomness

In 1985, Shafi Goldwasser, Silvio Micali, and Charles Rackoff introduced interactive proofs: a prover and a verifier exchange messages, and the verifier uses randomness to catch a lying prover89. This gave a probabilistic definition of knowledge and led to zero-knowledge proofs9. In 1990, Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan proved that every language in PSPACE has an interactive proof—a result that stunned the field, since it showed that randomness plus interaction could verify far more than anyone expected. The PCP theorem (Arora, Safra, and Arora, Lund, Motwani, Sudan, Szegedy, 1992) followed, connecting probabilistic verification to hardness of approximation.

Distributed computing and stochastic optimization

In distributed systems, randomness broke symmetry. In 1983, Alon Itai and Michael Rodeh gave a randomized algorithm for leader election in a ring; in the 1980s and 1990s, randomized consensus and Byzantine agreement protocols used coin flips to escape impossibility results that bind deterministic protocols under certain failure models. The randomized approach to distributed computing—where processors flip coins to agree—became a standard tool, later central to blockchain consensus.

Meanwhile, stochastic optimization—stochastic gradient descent, popularized for neural networks in the 1980s and 1990s—used random sampling of data to make large-scale learning tractable. The 2010s brought a rigorous theory of stochastic optimization and randomized algorithms for convex and nonconvex problems, connecting the field to machine learning.

The present

Today randomized algorithms are everywhere: in hashing and databases, in cryptographic protocols, in approximation algorithms, in streaming systems, in machine learning, and in distributed ledgers. The great open question remains the one Gill posed in 1977—whether $BPP = P$—and the derandomization program has reframed it as a question about computational hardness. The practical lesson of the history is that randomness is not a substitute for understanding but a way of exploiting it: a coin flip can stand in for a proof, a sample for a sum, a sketch for a stream. The field's practitioners still teach the same bargain, and still find new problems where the coins pay off.

References

  1. Randomized algorithm (introduction, Motivation, Data structures, Derandomization, Where randomness helps, Implicit uses in combinatorics, Randomized incremental constructions in geometry), Wikipedia
  2. Monte Carlo method (History), Wikipedia
  3. Miller–Rabin primality test, Wikipedia
  4. Universal hashing, Wikipedia
  5. Probabilistic method, Wikipedia
  6. Markov chain Monte Carlo (History), Wikipedia
  7. Metropolis–Hastings algorithm (History), Wikipedia
  8. IP (complexity), Wikipedia
  9. Zero-knowledge proof (History), Wikipedia

The frameworks of Randomized Algorithms

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1946-Present

    Monte Carlo method

    How can random sampling estimate hard quantities?

    Fly to its tower in Nousfarer

  2. 1947-Present

    Probabilistic method and derandomization

    When does a random object with a property exist?

    Fly to its tower in Nousfarer

  3. 1951-Present

    Stochastic gradient methods

    How do noisy observations guide optimization?

    Fly to its tower in Nousfarer

  4. 1953-Present

    Markov chain Monte Carlo

    How can a Markov chain sample a complex distribution?

    Fly to its tower in Nousfarer

  5. 1976-Present
  6. 1977-Present

    Probabilistic complexity theory

    Does randomness add power to efficient computation?

    Fly to its tower in Nousfarer

  7. 1977-Present
  8. 1979-Present

    Universal hashing

    Can hashing guarantee good performance on any input?

    Fly to its tower in Nousfarer

  9. 1981-Present

    Streaming algorithm

    How can a stream be summarized in small space?

    Fly to its tower in Nousfarer

  10. 1982-Present

    Derandomization and pseudorandomness

    Can randomness be replaced by pseudorandomness?

    Fly to its tower in Nousfarer

  11. 1982-Present
  12. 1983-Present

    Randomized distributed computing

    What can distributed processors achieve with random choices?

    Fly to its tower in Nousfarer

  13. 1985-Present
  14. 1985-Present

    Stochastic optimization

    How can noisy estimates drive optimization?

    Fly to its tower in Nousfarer

  15. 1987-Present

    Randomized rounding

    How can random rounding turn fractions into good integers?

    Fly to its tower in Nousfarer

  16. 1989-Present

    Randomized incremental construction

    How does random insertion order simplify geometry?

    Fly to its tower in Nousfarer

  17. 2000-Present

    Randomized numerical linear algebra

    How can random sampling speed up matrix computations?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Monte Carlo methodProbabilistic method and derandomizat…Stochastic gradient methodsMarkov chain Monte CarloRandomized primality and witness test…Probabilistic complexity theoryRandomized fingerprinting and verific…Universal hashingStreaming algorithmDerandomization and pseudorandomnessRandomized symmetry breaking in distr…Randomized distributed computingInteractive proofs and probabilistica…Stochastic optimizationRandomized roundingRandomized incremental constructionRandomized numerical linear algebra

Beyond the field

Where Randomized Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 75 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Randomized Algorithms is a planet in Nousfarer

Its city has a tower for each of these 17 frameworks. Land, walk in, and climb one concept at a time.

Land on Randomized Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Randomized Algorithms sits on the Map of Human Knowledge