- Atlas
- Computer Science
- Randomized Algorithms
Randomized Algorithms
A randomized algorithm is a procedure that flips coins as it runs.
17 frameworks, from 1946 to today · Algorithms · Computer Science
- Monte Carlo method 1946-Present
- Probabilistic method and derandomization 1947-Present
- Stochastic gradient methods 1951-Present
- Markov chain Monte Carlo 1953-Present
- Randomized primality and witness testing 1976-Present
- Probabilistic complexity theory 1977-Present
- Randomized fingerprinting and verification 1977-Present
- Universal hashing 1979-Present
- Streaming algorithm 1981-Present
- Derandomization and pseudorandomness 1982-Present
- Randomized symmetry breaking in distributed computing 1982-Present
- Randomized distributed computing 1983-Present
- Interactive proofs and probabilistically checkable proofs 1985-Present
- Stochastic optimization 1985-Present
- Randomized rounding 1987-Present
- Randomized incremental construction 1989-Present
- Randomized numerical linear algebra 2000-Present
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
- Randomized algorithm (introduction, Motivation, Data structures, Derandomization, Where randomness helps, Implicit uses in combinatorics, Randomized incremental constructions in geometry), Wikipedia
- Monte Carlo method (History), Wikipedia
- Miller–Rabin primality test, Wikipedia
- Universal hashing, Wikipedia
- Probabilistic method, Wikipedia
- Markov chain Monte Carlo (History), Wikipedia
- Metropolis–Hastings algorithm (History), Wikipedia
- IP (complexity), Wikipedia
- 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.
- 1946-Present
- 1947-Present
Probabilistic method and derandomization
When does a random object with a property exist?
- 1951-Present
Stochastic gradient methods
How do noisy observations guide optimization?
- 1953-Present
Markov chain Monte Carlo
How can a Markov chain sample a complex distribution?
- 1976-Present
Randomized primality and witness testing
Can random witnesses certify primality?
- 1977-Present
Probabilistic complexity theory
Does randomness add power to efficient computation?
- 1977-Present
Randomized fingerprinting and verification
Can random hashes verify equality cheaply?
- 1979-Present
- 1981-Present
- 1982-Present
Derandomization and pseudorandomness
Can randomness be replaced by pseudorandomness?
- 1982-Present
Randomized symmetry breaking in distributed computing
How do coins break symmetry among processors?
- 1983-Present
Randomized distributed computing
What can distributed processors achieve with random choices?
- 1985-Present
Interactive proofs and probabilistically checkable proofs
How can randomness make proofs convincing?
- 1985-Present
- 1987-Present
Randomized rounding
How can random rounding turn fractions into good integers?
- 1989-Present
Randomized incremental construction
How does random insertion order simplify geometry?
- 2000-Present
Randomized numerical linear algebra
How can random sampling speed up matrix computations?
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.
Markov chain Monte Carlo influenced by Monte Carlo method
The Metropolis algorithm, published in 1953, was developed in the same Los Alamos statistical-physics milieu as the Monte Carlo method and used random sampling of configurations to estimate thermal averages, making it a direct descendant of the earlier sampling approach.
Carried by Nicholas Metropolis; Stanislaw Ulam.
Derandomization and pseudorandomness grew out of Probabilistic method and derandomization
Derandomization grew directly out of the probabilistic method: the method of conditional probabilities turns Erdős-style existence proofs into deterministic constructions, and pseudorandom generators were developed to replace the random objects those proofs assumed.
Carried by Paul Erdős; Russell Impagliazzo; Avi Wigderson.
Stochastic optimization grew out of Stochastic gradient methods
Stochastic optimization grew out of stochastic approximation: Robbins–Monro-style iterative updates using noisy gradient estimates became the core of stochastic gradient descent and its optimization theory.
Carried by Herbert Robbins; Sutton Monro.
Derandomization and pseudorandomness grew out of Probabilistic complexity theory
Derandomization and pseudorandomness were framed as the campaign to answer the BPP-versus-P question that Gill's class definitions had posed, with hardness-to-randomness results aimed at proving BPP = P.
Carried by Russell Impagliazzo; Avi Wigderson; Noam Nisan.
Randomized primality and witness testing influenced by Monte Carlo method
The randomized primality tests of Rabin and of Solovay–Strassen applied the Monte Carlo idea of repeated random trials with exponentially shrinking error to number theory, turning Lehmer's earlier randomized test into a general template.
Carried by Michael Rabin; Robert Solovay; Volker Strassen.
Probabilistic complexity theory influenced by Monte Carlo method
Gill's definition of BPP formalized the bounded-error behavior of Monte Carlo algorithms into a complexity class, giving the sampling paradigm a place in complexity theory.
Carried by John Gill.
Randomized fingerprinting and verification influenced by Monte Carlo method
Karp and Lipton's randomized fingerprinting and Freivalds' matrix-verification test used random sampling to check equality cheaply, extending the Monte Carlo principle from estimation to verification.
Carried by Richard Lipton; Robert Freivalds.
Streaming algorithm influenced by Monte Carlo method
Flajolet and Martin's distinct-elements estimator used hashing and random bit patterns to sample a stream, carrying the Monte Carlo sampling idea into the streaming setting.
Carried by Philippe Flajolet; G. Nigel Martin.
Randomized numerical linear algebra influenced by Monte Carlo method
Randomized numerical linear algebra samples rows or columns and uses random projections to approximate matrix computations, extending Monte Carlo sampling to large-scale linear algebra.
Carried by Petros Drineas; Michael Mahoney.
Randomized rounding influenced by Probabilistic method and derandomization
Randomized rounding uses the probabilistic method's existence arguments together with Chernoff bounds to show that a random rounding of an LP solution is close to optimal with high probability.
Carried by Prabhakar Raghavan; Clark Thompson.
Probabilistic complexity theory influenced by Randomized primality and witness testing
The one-sided and bounded-error behavior of the randomized primality tests provided the concrete model from which Gill abstracted the classes RP, ZPP and BPP.
Carried by John Gill; Michael Rabin.
Interactive proofs and probabilistically checkable proofs influenced by Probabilistic complexity theory
Interactive proofs were defined as probabilistic complexity classes with a randomized verifier, building on the BPP-style model of bounded-error randomized computation.
Carried by Shafi Goldwasser; Silvio Micali; Charles Rackoff.
Streaming algorithm influenced by Universal hashing
Universal hashing supplied the collision-probability guarantees that streaming sketches rely on when they hash stream elements into buckets.
Carried by J. Lawrence Carter; Mark Wegman.
Derandomization and pseudorandomness influenced by Universal hashing
Universal hash families became a standard building block in pseudorandom generator constructions and derandomization, where they supply limited independence from few random bits.
Carried by J. Lawrence Carter; Mark Wegman.
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.
Monte Carlo method led to Markov chain Monte Carlo in Statistical Computing
MCMC is a specialized Monte Carlo method, descending from the general Monte Carlo technique developed in the 1940s. The Metropolis algorithm applied Monte Carlo sampling within a Markov chain framework.
Carried by Metropolis et al. (1953).
Monte Carlo method influenced by Stochastic process in Probability Theory
Ulam and von Neumann's sampling scheme was framed and analyzed in the language of stochastic processes, notably Markov chains; the method's convergence arguments drew directly on the theory of random processes developed earlier by Markov and Kolmogorov.
Carried by Stanislaw Ulam; John von Neumann.
Probabilistic method and derandomization influenced Randomization and Probabilistic Distributed Computing in Distributed Algorithms
The probabilistic method, developed by Erdős and others from the 1940s, supplied the existence arguments and random-choice techniques that randomized distributed algorithms later adapted to break symmetry and bound expected time. The 1983 randomized consensus and symmetry-breaking work drew directly on these combinatorial tools.
Probabilistic method and derandomization influenced Randomized Computation and Derandomization in Complexity Theory
The probabilistic method, developed by Erdős and others from the late 1940s, supplied the technique of proving existence by showing a random object has positive probability of the desired property. Derandomization research in randomized computation took this method up and asked how to convert such existence proofs into explicit deterministic constructions, notably through conditional expectations and the method of conditional probabilities.
Carried by Paul Erdős; Method of Conditional Probabilities.
Stochastic gradient methods influenced Policy gradient method in Reinforcement Learning
Stochastic gradient methods, especially Robbins-Monro stochastic approximation, are the mathematical engine of policy gradient: Williams' REINFORCE and later policy-gradient theorems estimate policy gradients by stochastic approximation.
Carried by Herbert Robbins; Sutton Monro.
Markov chain Monte Carlo influenced by Markov chain in Markov Processes
Metropolis and colleagues' sampling scheme relies directly on Markov chain theory: they construct a chain whose stationary distribution is the target. Markov's original analysis of chains supplied the convergence machinery.
Carried by Andrey Markov; Nicholas Metropolis.
Markov chain Monte Carlo influenced by Markov chain in Stochastic Processes
The same Markov chain theory, stated under the Stochastic Processes label, underpins the Metropolis algorithm's construction and convergence arguments.
Carried by Andrey Markov; Nicholas Metropolis.
Probabilistic complexity theory influenced Probabilistically Checkable and Interactive Proofs in Proof Complexity
Probabilistic complexity theory supplied the classes (BPP, IP, PSPACE) and the randomised-verifier model on which interactive proofs and the PCP theorem were built. The definitions of interactive proof and PCP are stated in its terms.
Probabilistic complexity theory influenced by Randomized algorithm in Computational Number Theory
The randomized algorithms of the mid-1970s, above all Solovay–Strassen and Miller–Rabin primality testing, supplied the concrete examples from which Gill and others abstracted the probabilistic complexity classes BPP and RP.
Carried by John Gill; Michael Rabin.
Probabilistic complexity theory influenced Interactive Proofs and Probabilistically Checkable Proofs in Complexity Theory
Probabilistic complexity theory supplied the randomized verification model and the class BPP that Goldwasser, Micali and Rackoff generalized into interactive proofs. The IP model was defined by adding interaction to probabilistic polynomial-time verification.
Carried by Shafi Goldwasser; Silvio Micali; Charles Rackoff.
Streaming algorithm led to Sliding-Window and Time-Decay Models in Streaming Algorithms
Sliding-window and time-decay models are streaming algorithms, extending the streaming model with recency-weighted or windowed queries.
Streaming algorithm led to Graph Streaming and Sparsification in Streaming Algorithms
Graph streaming is a specialization of the general streaming-algorithm model, applying its single-pass, sublinear-space constraints to graph problems. The graph-streaming literature explicitly frames itself as streaming algorithms for graphs.

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 AlgorithmsRelated fields
Fields its ideas are linked to
- Distributed Algorithms 10 links
- Algorithms 9 links
- Complexity Theory 7 links
- Graph Algorithms 5 links
- Computational Number Theory 5 links
- Streaming Algorithms 4 links
- Probability Theory 3 links
- Reinforcement Learning 2 links
- Linear Algebra 2 links
- Numerical Analysis 2 links
- Probabilistic Combinatorics 2 links
- Statistical Computing 2 links
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Streaming Algorithms
- String Algorithms
See where Randomized Algorithms sits on the Map of Human Knowledge