A randomized algorithm is an algorithm that uses random choices as part of its computation. For a fixed input, different choices may produce different execution paths, running times, or outputs. Its guarantees are therefore expressed using probability, rather than solely through deterministic bounds. Randomization can simplify algorithm design, reduce computational cost, or provide efficient approximate answers. It does not necessarily introduce incorrect results: some randomized algorithms always return a correct answer, while others permit a controlled probability of error. (cs.yale.edu)
Computational model and analysis
A randomized algorithm can be represented as (A(x,r)), where (x) is the input and (r) is a sequence of random bits. Once both are fixed, the computation is deterministic. The standard theoretical model supplies independent, unbiased bits; algorithms may use them to sample from a uniform distribution or construct other random choices. A probabilistic Turing machine formalizes this model for computational complexity theory. (cs.yale.edu)
The crucial distinction from average-case analysis is where randomness occurs. Average-case analysis assumes a distribution over inputs; randomized analysis can hold for every fixed input, with probability taken only over the algorithm’s internal choices. Thus a difficult input need not invalidate an expected-performance guarantee. This distinction also requires stating whether the input is fixed independently of those choices. (theory.cs.princeton.edu)
Running time becomes a random variable (T(x,r)). An expected-time bound concerns its expected value, such as (\mathbb{E}_r[T(x,r)]). A high-probability bound instead limits the chance that execution exceeds a specified threshold. These are distinct guarantees: a small expectation alone does not exclude occasional long executions. Analyses may separately bound running time, output error, and approximation quality. (cs.yale.edu)
Las Vegas and Monte Carlo algorithms
A Las Vegas algorithm never returns an incorrect answer. Its running time may depend on random choices, and efficiency is often measured in expectation. An equivalent formulation allows a bounded-time attempt to report a recognizable failure, followed by another attempt. Randomized sorting provides a familiar example: randomness changes the work performed, not the required ordering of the result. (cs.yale.edu)
A Monte Carlo algorithm has a bounded running-time guarantee but may return an incorrect answer with a specified probability. One-sided error means that only one answer category can be mistaken; two-sided error permits mistakes in either category. The name is related to the broader Monte Carlo method, which estimates quantities through random sampling. (cs.yale.edu)
The categories describe guarantees rather than rigid implementation types. A Las Vegas procedure can be stopped after a time limit and made to return a default answer, introducing possible error. Conversely, if a candidate result can be checked efficiently, repeated generation and verification may yield a zero-error procedure; its expected efficiency depends on the success probability and verification cost. (cs.yale.edu)
Representative algorithms
Randomized quicksort. Quicksort chooses a pivot, partitions the input, and sorts the resulting parts by recursion. Choosing each pivot uniformly at random gives expected (O(n\log n)) work for every fixed input under standard assumptions. The worst execution can still require (O(n^2)) work. It is a Las Vegas algorithm because pivot choices do not compromise correctness. The bounds use big-O notation to describe asymptotic time complexity. (cs.cmu.edu)
Random contraction. In graph theory, Karger’s algorithm finds a global minimum cut by repeatedly contracting uniformly selected edges until two supervertices remain. For a connected undirected multigraph with (n\geq2) vertices, one run succeeds with probability at least (2/[n(n-1)]). Repeating the procedure independently and retaining the smallest cut found improves the success probability. (cs.yale.edu)
Randomized matrix computation. Methods in numerical linear algebra use random sampling or projections to construct smaller representations, called sketches, of a matrix. Computation on these sketches can approximate least-squares solutions or low-rank factorizations. Their guarantees relate the reduced computational cost to approximation error and failure probability. (arxiv.org)
Error reduction
Probability amplification improves reliability through repetition. If a decision algorithm succeeds with probability at least (2/3) on every input, independently repeating it and taking a majority vote reduces the error exponentially in the number of repetitions. Consequently, (O(\log(1/\delta))) repetitions suffice for error at most (\delta). Independence is important: repeating an identical random execution does not provide fresh evidence. (theory.cs.princeton.edu)
The aggregation rule depends on the problem. Majority voting suits two-sided decision errors; one-sided tests can use an appropriate acceptance or rejection rule. For random contraction, the smallest observed cut is retained because every generated cut is valid, although it may not be optimal. (theory.cs.princeton.edu)
Complexity classes and implementation
For decision problems, BPP denotes polynomial-time randomized computation with bounded two-sided error. RP allows false negatives but no false positives; coRP reverses that asymmetry. ZPP comprises problems solvable without error in expected polynomial time. These classes formalize different combinations of efficiency and reliability. (theory.cs.princeton.edu)
Derandomization seeks to replace random choices with deterministic computation while preserving efficiency. Whether every BPP problem belongs to deterministic polynomial time remains a central open question. Enumerating all random-bit sequences provides a basic simulation, but its cost is generally exponential in the number of bits used. (people.eecs.berkeley.edu)
Implementations commonly obtain choices from a pseudorandom number generator, which deterministically expands an initial state. Reusing a seed under compatible generator conditions supports reproducibility, although software versions and execution details can matter. Statistical usefulness does not imply suitability for cryptography: ordinary pseudorandom generators may be predictable and are not interchangeable with cryptographically secure randomness. (docs.python.org)
References
- Notes on Randomized Algorithmscs.yale.edu
- Randomized Computationtheory.cs.princeton.edu
- Chapter 7: Randomized Algorithmscs.cmu.edu
- RandomizedAlgorithmscs.yale.edu
- Randomized algorithms for matrices and dataarxiv.org
- 895 Randomness and Computationpeople.csail.mit.edu
- random — Generate pseudo-random numbersdocs.python.org