Randomized algorithm

Randomized algorithms use random choices as part of their computational procedure, so one input can produce different execution traces on different runs.¹ The randomness may select a pivot, sample data, choose a search path, or decide whether to repeat a test. Analysis therefore considers probability distributions over executions rather than one fixed sequence of operations.

Two broad classes organize the subject. A Las Vegas algorithm always returns a correct answer, while its running time or amount of work is random; randomized quicksort is a standard example. A Monte Carlo algorithm has a bounded or predictable running time but accepts a small probability of an incorrect answer. Error can often be reduced by independent repetition, although the cost and dependence between trials must be analyzed carefully.

Randomization is useful because it can make algorithms simpler, faster on average, and less vulnerable to unfavorable input arrangements. Randomized quicksort avoids the consistently poor pivot choices that can make a fixed pivot rule take quadratic time, achieving expected O(n log n) comparisons under common models.² In streaming and sublinear algorithms, random samples or compact sketches estimate properties of data without reading or storing everything.

Randomness also helps defeat adversarial behavior. In online settings, an opponent that knows a deterministic policy can construct inputs against it, whereas a private random choice can make such prediction difficult. Randomized algorithms appear in cryptography, distributed computing, load balancing, geometric sampling, approximation algorithms, and randomized primality testing. Their guarantees may be stated as expected running time, high-probability success, or bounds that hold for every input while averaging only over internal random choices.

Analyzing a randomized algorithm requires specifying both the input model and the source of randomness. Expected performance over random inputs is not the same as performance guaranteed for every input, and an algorithm that is fast on average may still have rare, expensive executions. Tail bounds, concentration inequalities, and failure-probability calculations help distinguish a dependable high-probability guarantee from a merely favorable mean.

Practical implementations usually use pseudorandom number generators, whose deterministic output is designed to imitate random behavior. This makes experiments reproducible through a seed, but it does not automatically provide cryptographic security. Security-sensitive algorithms require carefully designed random or pseudorandom sources, because predictable choices can reveal keys or undermine protocols.³ Correlated, biased, or reused random values can likewise invalidate a proof that assumes independent samples.

Randomized algorithms have important middle ground between exact computation and pure approximation. Randomized rounding converts fractional solutions into discrete ones while preserving expected objective values, often yielding provable approximation guarantees for difficult optimization problems.⁴ Random walks support algorithms for graph connectivity, sampling, ranking, and estimating algebraic quantities; their behavior connects algorithm design with probability theory and Markov chains.

Randomness can also be removed in principle through derandomization, replacing random choices with carefully selected deterministic ones, though the resulting algorithm may be more complicated or slower. In complexity theory, randomized classes such as BPP formalize problems solvable with bounded error in polynomial time, and major results show that some apparently random advantages may be reproducible deterministically under additional assumptions. The field thus studies not only how to use randomness, but also when it is genuinely necessary.

Las Vegas algorithm

A randomized algorithm that always produces a correct result, with randomness affecting its running time or resource use.

Monte Carlo algorithm

A randomized algorithm with a bounded or controlled running time that may return an incorrect result with small probability.

Derandomization

The transformation of a randomized algorithm into a deterministic one while preserving useful performance or correctness guarantees.

High-probability guarantee

A claim that an event occurs with probability at least 1 minus a small error parameter.