Loading field map
Randomized algorithms are computational procedures that make deliberate use of randomness as a resource in their design and execution. Unlike deterministic algorithms, whose every step is fixed in advance, a randomized algorithm consults a source of random bits during its run, and its behavior—the sequence of steps it takes, the intermediate values it computes, and sometimes even its final output—can vary from one run to the next. The central intellectual move of the field is to show that, despite this variability, such algorithms can solve problems correctly and efficiently, often with guarantees that are stronger or simpler than those available to deterministic methods.
The subfield sits at the intersection of algorithm design, probability theory, and computational complexity. Its practitioners ask not only "Can this problem be solved efficiently?" but also "Can it be solved efficiently with randomness, and what does randomness buy us?" The stakes are both practical and theoretical. Randomness appears in real systems—from cryptographic protocols to machine learning pipelines to network routing—and randomized algorithms are among the most widely deployed tools in computing. At the same time, the question of whether randomness is truly necessary for efficient computation remains one of the deepest open problems in computer science.
To understand randomized algorithms, it helps to distinguish the different ways randomness can enter a computation. The most common model, introduced in the 1970s, is the probabilistic Turing machine: a standard Turing machine augmented with the ability to flip a fair coin at each step. The machine's computation is a random variable, and its correctness and running time are assessed probabilistically.
Two broad classes of randomized algorithms emerged from this model. Las Vegas algorithms always produce the correct answer, but their running time is a random variable; the algorithm is guaranteed to terminate correctly, and the expected running time is bounded. The classic example is randomized quicksort, which picks a random pivot at each recursive step. Its worst-case running time is quadratic, but with random pivots, the expected running time is \(O(n \log n)\), and the probability of a slow run decays rapidly. Monte Carlo algorithms, by contrast, have a fixed running time but may err with small probability. A Monte Carlo algorithm for a decision problem might be required to answer "yes" correctly with probability at least \(2/3\), while always answering "no" correctly; by repeating the algorithm many times and taking a majority vote, the error probability can be driven down exponentially. The distinction between the two classes is not absolute—a Las Vegas algorithm can be converted into a Monte Carlo algorithm by truncating its running time, and a Monte Carlo algorithm with a verifiable output can sometimes be converted into a Las Vegas one—but the two labels capture a real difference in what kind of guarantee an algorithm offers.
A deeper question concerns the source and quality of the randomness itself. Most theoretical work assumes access to a stream of independent, unbiased random bits. In practice, true randomness is hard to obtain, and algorithms typically use pseudorandom generators: deterministic functions that expand a short random seed into a long sequence that "looks random" to the algorithm at hand. The study of pseudorandomness is tightly interwoven with randomized algorithms, because a pseudorandom generator that fools a particular class of algorithms can derandomize them—that is, replace their random bits with a deterministic sequence while preserving correctness.
Randomized techniques entered algorithm design through a series of influential results in the 1970s and 1980s. One early landmark was the Miller–Rabin primality test, which determines whether a large integer is prime. Deterministic primality testing was known to be possible, but the fastest deterministic algorithms were slow and complicated. Miller–Rabin, by contrast, is simple, fast, and Monte Carlo: it either reports "composite" with certainty or "probably prime" with a small error probability that can be made arbitrarily small by repetition. For decades, this was the test used in practice for cryptographic key generation, and it remains a standard tool.
Another foundational result was the randomized algorithm for the minimum cut problem, due to David Karger and Clifford Stein in the early 1990s. The algorithm repeatedly contracts randomly chosen edges of a graph until only two vertices remain; the edges between them form a cut. With surprisingly high probability, this simple procedure finds a minimum cut, and repeating it a modest number of times yields a Monte Carlo algorithm that is both simpler and faster than the best known deterministic algorithms of its time. The result was striking because it showed that a natural, almost naive use of randomness could outperform sophisticated deterministic constructions.
Around the same period, randomized rounding emerged as a powerful technique for approximation algorithms. Many combinatorial optimization problems—such as set cover, max-cut, and various scheduling problems—are NP-hard, meaning that exact solutions are believed to require exponential time. Approximation algorithms aim to find solutions provably close to optimal. Randomized rounding takes a fractional solution to a linear programming relaxation of the problem and rounds each variable to an integer randomly, with probabilities derived from the fractional values. The resulting integer solution is often a good approximation, and probabilistic analysis can bound its quality. This technique, pioneered by Prabhakar Raghavan and Clark Tompson in the 1980s, turned linear programming—a deterministic tool—into a source of randomized algorithms with rigorous guarantees.
These successes, along with many others, established randomization as a mainstream technique in algorithm design. By the 1990s, randomized algorithms were a standard topic in textbooks and graduate curricula, and the field had developed a rich toolkit of methods.
The practice of randomized algorithms is organized less by competing schools than by a set of recurring techniques, each suited to particular kinds of problems. Understanding these techniques is the key to navigating the field.
Sampling and estimation is the most direct use of randomness. When a quantity is too large or too complex to compute exactly, a randomized algorithm can estimate it by drawing random samples and averaging. The Monte Carlo method for numerical integration, developed in the 1940s for physics problems, is the ancestor of this approach. In computer science, sampling underlies algorithms for estimating the size of a database query result, the number of distinct elements in a stream, or the volume of a convex body. The Chernoff bound and related concentration inequalities provide the mathematical backbone: they quantify how tightly the average of many independent random samples concentrates around the true expectation, allowing the algorithm designer to trade sample size against accuracy and confidence.
Randomized hashing uses randomness to distribute data uniformly across buckets or to assign fingerprints to large objects. A universal family of hash functions is a set of functions from a large domain to a small range, chosen randomly, such that any two distinct inputs collide with low probability. Universal hashing underlies efficient hash tables, load balancing, and the Bloom filter, a space-efficient probabilistic data structure for membership testing that may report false positives but never false negatives. Randomized hashing also appears in fingerprinting, where a large object (such as a file or a polynomial) is mapped to a short random string; two objects are compared by comparing their fingerprints, with a small probability of a false match.
Randomized search and optimization covers algorithms that use randomness to explore a space of solutions. The most famous example is the Metropolis–Hastings algorithm and its generalization, Markov chain Monte Carlo (MCMC). These methods define a Markov chain whose stationary distribution is the target distribution of interest, then simulate the chain to draw samples from that distribution. MCMC is the workhorse of Bayesian statistics, statistical physics, and computational biology. In algorithm design, a related idea appears in simulated annealing, which randomly perturbs a candidate solution while gradually lowering a "temperature" parameter, allowing the search to escape local optima. These methods are often heuristic in practice, but for certain problems—such as sampling from the set of perfect matchings in a graph—MCMC algorithms come with rigorous polynomial-time guarantees.
Randomized rounding, mentioned above, is a bridge between optimization and probability. It is particularly powerful for problems with a linear programming relaxation, because the fractional solution encodes probabilistic information about which variables are likely to be set to 1 in a good integer solution. The technique has been refined in many directions, including dependent rounding, which correlates the rounding decisions to preserve additional constraints, and Lovász local lemma–based algorithms, which handle rare bad events by showing that they can be avoided with positive probability and then finding a good outcome efficiently.
Randomized algorithms for algebraic problems exploit the fact that random evaluations can certify identities. The classic example is polynomial identity testing: given an arithmetic circuit computing a polynomial, determine whether the polynomial is identically zero. The deterministic version of this problem is believed to be hard, but a randomized algorithm simply evaluates the polynomial at a few random points; if the polynomial is nonzero, it vanishes at a random point with low probability. This simple idea underlies many results in algebraic complexity and is also used in program testing and in the verification of matrix identities.
Derandomization is the complementary enterprise: showing that randomness can be eliminated without much loss in efficiency. The central tool is the pseudorandom generator, a deterministic function that expands a short seed into a long bit string that no algorithm from a given class can distinguish from truly random bits. If such generators exist with short seeds, then any randomized algorithm in that class can be simulated deterministically by enumerating all seeds. The hardness versus randomness paradigm, developed in the 1980s and 1990s, connects this question to computational hardness: if certain problems are hard to compute, then pseudorandom generators exist, and randomness can be eliminated. This line of work has produced conditional derandomizations for broad classes of algorithms, but the unconditional derandomization of all polynomial-time randomized algorithms remains open.
The most fundamental open question in the field is whether randomness actually helps. The class BPP (bounded-error probabilistic polynomial time) consists of decision problems solvable by a randomized polynomial-time algorithm that errs with probability at most \(1/3\). The class P consists of problems solvable by deterministic polynomial-time algorithms. The question "Is P = BPP?" asks whether every problem that can be solved efficiently with randomness can also be solved efficiently without it. Most researchers believe the answer is yes, and substantial evidence supports this belief: under plausible hardness assumptions, $P = BPP$. But no unconditional proof is known, and the question remains open.
A related but distinct question concerns the power of randomness in other computational settings. For example, randomized communication complexity studies how much information two parties must exchange to compute a function when they are allowed to use shared or private randomness; in some cases, randomness dramatically reduces the required communication. Similarly, randomized decision trees and randomized circuits define complexity classes that may differ from their deterministic counterparts. These settings are not merely academic: they model distributed computing, cryptography, and the power of sampling in interactive protocols.
The relationship between randomness and cryptography is particularly delicate. Cryptographic protocols require randomness to generate keys, choose nonces, and hide information; a deterministic protocol is often insecure by construction. At the same time, cryptography provides some of the strongest evidence that randomness is useful, because breaking many cryptographic schemes is believed to be hard, and the security proofs rely on the adversary's inability to predict random choices. The study of randomness extractors—functions that convert imperfect sources of randomness into nearly uniform random bits—connects cryptography, pseudorandomness, and information theory, and has applications in both theoretical and practical settings.
In practice, randomized algorithms are everywhere, often in places where their probabilistic nature is hidden from the end user. Hash tables in programming languages use randomized hashing to prevent denial-of-service attacks that exploit worst-case collision patterns. Streaming algorithms for network monitoring, such as HyperLogLog for counting distinct elements, use randomization to achieve dramatic space savings with small error. Machine learning pipelines rely on stochastic gradient descent, which injects randomness into the optimization process to escape poor local minima and to scale to massive datasets. Cryptographic systems, from TLS to blockchain protocols, depend on random number generation for their security guarantees.
A recurring practical concern is the quality of the randomness source. Many real-world systems have been compromised because their random number generators were predictable, either due to insufficient entropy or due to flawed implementation. This has motivated the design of cryptographically secure pseudorandom generators, which produce bits that are computationally indistinguishable from random, and of randomness extractors, which distill high-quality randomness from noisy physical sources. The gap between the theoretical assumption of perfect randomness and the messy reality of physical entropy is a persistent theme in applied randomized algorithms.
Another practical theme is the trade-off between randomized and deterministic methods. In many settings, a randomized algorithm is simpler, faster, or easier to implement than its deterministic counterpart, but the probabilistic guarantee may be unacceptable for safety-critical applications. In such cases, the algorithm can be derandomized using the method of conditional expectations or other techniques, often at the cost of some efficiency. The choice between a Monte Carlo algorithm with a tiny error probability and a deterministic algorithm with a slightly worse running time is a judgment call that depends on the application.
Randomized algorithms are not a niche subfield but a fundamental mode of computation. They demonstrate that allowing a controlled amount of unpredictability can yield algorithms that are simpler, faster, and more robust than their deterministic counterparts. The field has produced both practical tools of enormous reach and deep theoretical questions that touch on the nature of efficient computation itself.
The intellectual legacy of randomized algorithms is also visible in how it reshaped the broader discipline. The probabilistic method—proving the existence of an object by showing that a random construction succeeds with positive probability—has become a standard tool in combinatorics and computer science. The study of pseudorandomness has forged deep connections between algorithms, complexity theory, and cryptography. And the ongoing investigation of whether randomness can be eliminated has clarified the boundaries of efficient computation, even where the boundaries remain unknown.
For the educated newcomer, the field is best understood not as a collection of tricks but as a coherent way of thinking: identify where a problem's difficulty comes from, introduce randomness to break the symmetry or spread the risk, and then use probabilistic analysis to show that the risk is controlled. That pattern recurs across every technique described here, from sampling to hashing to rounding to derandomization. It is a way of designing algorithms that embraces uncertainty as a resource rather than a nuisance, and it has proven to be one of the most durable and generative ideas in computer science.