Randomized Algorithm¶
A randomized algorithm makes internal random choices and states its output or cost guarantee over those choices for each fixed input.
Core Idea¶
A randomized algorithm has an ordinary problem input and a second, internally supplied sequence of random choices. Holding the input fixed while varying those choices can change the execution path, time, or returned answer. A useful guarantee therefore says what happens over the choices for each input: expected running time, a high-probability bound, or a controlled chance of error. This is distinct from timing a deterministic program on a random sample of inputs. MIT's randomized-quicksort notes explicitly say its expected bound holds for every input array.[1][2]
The two familiar contracts are alternatives. A Las Vegas algorithm never returns an incorrect answer but can take a random amount of time; random-pivot quicksort fits that pattern. A Monte Carlo algorithm bounds its work while accepting a bounded failure probability; Karger's simple contraction run can return a nonminimum cut, and independent reruns improve the probability that the smallest returned cut is minimum. The labels do not imply that either type is invariably faster than a deterministic competitor.[1][2][3]
Structural Signature¶
Sig role-phrases:
- Fixed problem instance: an array, graph or other input remains fixed during the probability calculation.
- Internal random source: fresh bits choose pivots, edges, samples or witnesses according to a stated distribution.
- Choice-dependent execution: different coin sequences can produce different traces, costs or outputs.
- Per-input guarantee: the algorithm's contract quantifies over those traces, not merely over a convenient population of inputs.
- Repetition policy: where failure can occur, suitably independent runs may reduce its chance; this is optional, not part of every randomized algorithm.[1][2]
Condensed: fixed input + internal random choice → distribution of executions → per-input cost/correctness statement.
What It Is Not¶
A deterministic sort measured on shuffled data is not randomized merely because the experimenter randomized the data. A procedure that reads random bits but never lets them affect a branch, operation or output has no substantive randomized mechanism. A single run of a pseudorandom generator with an already fixed seed is deterministic conditional on that seed; one must say how seeds are sampled or which computational assumption replaces ideal random bits. Nor is probabilistic correctness the definition: quicksort's answer remains correct even when its chosen pivots are disastrous for time.[1]
Scope of Application¶
In sorting, a uniformly random pivot removes the simple adversarial relationship between a fixed input ordering and a deterministic pivot rule. The expected \(O(n\log n)\) cost is over pivots on every array, not a promise that no run is quadratic. In graph optimization, random edge contraction offers a different payoff: one run may miss a minimum cut, but avoiding the edges of a selected minimum cut at each contraction has a calculable positive probability; rerunning and keeping the smallest cut raises success probability.[1][2][3]
Sampling, randomized hashing, fingerprinting and randomized incremental geometry share the internal-choice structure but need their own error and runtime analyses. The present evidence specifically supports sorting and min-cut; it does not justify universal claims about security, physical entropy or every pseudorandom implementation.
Clarity¶
Ask three questions of any claim. What is fixed? What is sampled? Which quantity is bounded? For quicksort the array is fixed, pivots are sampled, and comparison cost is a random variable while correctness is invariant. For contraction the graph is fixed, edges are sampled, and success at retaining a minimum cut is random. “Average fast” is otherwise ambiguous: average over customers' inputs is a workload statement, while expected fast on every input is an algorithmic guarantee.[1][3]
Manages Complexity¶
The abstraction separates implementation behavior from its probability contract. Instead of cataloging every possible pivot sequence or edge sequence, an analysis groups runs by expected cost or a failure event. It also prevents a common conflation: an algorithm can have excellent expected time and a poor worst-case trace, or bounded work and a nonzero error chance. Stating the random variable and its sample space keeps these distinctions visible when moving between domains.
Abstract Reasoning¶
Take a sorted array of four distinct keys. Choosing the first key at every quicksort recursion causes the familiar one-sided recursion. Choosing 2 first divides the remaining keys into a one-key left side and a two-key right side. Neither event changes the correct final ordering; the random pivot only redistributes work. The MIT result scales this distinction: rare unfortunate traces coexist with \(O(n\log n)\) expected cost on each fixed array.[1]
For a fixed graph minimum cut, a contraction across that cut irrevocably destroys this candidate. A contraction elsewhere can preserve it. The probability of a run succeeding is thus a product of survival chances, not an assumption that graphs arrive randomly. A returned cut is still a genuine graph cut; the uncertainty is whether its value equals the optimum. Independent repetition changes the probability of finding the optimum, not the optimum itself.[2][3]
Knowledge Transfer¶
The shared skeleton transfers from divide-and-conquer sorting to graph contraction: a fixed input, internal choice distribution, a resulting family of executions, and a stated per-input guarantee. The guarantee does not transfer numerically. The quicksort pivot argument cannot be transplanted to min-cut, and a min-cut success bound says nothing about sorting time. The pattern travels only after the new domain supplies a valid probability analysis and an account of whether failure is detectable.
Examples¶
Four-key random-pivot quicksort¶
On the fixed ascending array [1, 2, 3, 4], a first pivot of 2 produces subproblems [1] and [3, 4]; first pivot 1, followed by similarly extreme pivots, produces a chain of unbalanced subproblems. Both paths return [1, 2, 3, 4]. They differ in comparisons. Uniform pivot sampling gives the expectation analyzed in the MIT notes; this small trace illustrates the mechanism rather than constituting the asymptotic proof.[1]
Mapped back: the array is the fixed instance; random pivot selections are the internal source; partition recursion is the choice-dependent execution; sorting correctness holds on both traces while expected work is quantified over pivot sequences; repetition is unnecessary for correctness.
Two doubled-edge pairs under contraction¶
Take a four-vertex multigraph: two parallel A—B edges, two parallel C—D edges and one bridge B—C. The bridge defines the unique size-one minimum cut. A first contraction within either pair has probability 4/5; then the remaining internal pair has two edges while the bridge has one, so a second safe contraction has conditional probability 2/3. Thus this simple run preserves the minimum cut with probability (4/5)×(2/3)=8/15. A contraction of the bridge instead destroys the unique optimum and leaves a larger returned cut. The general source proof handles arbitrary graphs; this small multigraph is an explicit derivation, not a source-reported experiment.[2][3]
Mapped back: the multigraph is fixed; chosen edges are internal randomness; contractions change the resulting two-supervertex partition; success means a returned cut of the true minimum value, and independent reruns with the smallest value retained increase the chance of seeing it.
Structural Tensions¶
Correctness protection versus bounded-work error. Quicksort can preserve correctness while randomizing work; a bounded sequence of contraction trials can cap effort while retaining a failure chance. Repeating the latter uses more work to improve confidence. These are alternative contracts, not an intrinsic benefit enjoyed by every random procedure. Diagnostic: which outcome is invariant, which is random, and does the proposed repetition actually use independent choices?[1][2]
An unlucky execution and a reliable distributional guarantee can coexist. The distinction belongs to the definition and analysis: for each fixed input, determine whether probability over internal choices bounds expected work, a tail event or answer error. It is not a second opposed design aim.[1][3]
Structural–Framed Character¶
The entry sits near the structural end: a fixed input, an internal random source and a probability contract determine the mechanism. Its evaluative weight enters when a designer judges whether expected cost, a tail bound or a residual error rate is acceptable for a task. Human practice chooses the random source and analyzes its assumptions, but no institution creates the mathematical distinction; teaching conventions stabilize the Las Vegas/Monte Carlo vocabulary. The vocabulary travels literally across sorting and graph algorithms when their probability spaces are specified. Importing “randomized” to a deterministic program fed random-looking data is not recognition of this algorithm family. Its character: a domain-specific method family defined by internal choice and per-input probabilistic guarantees, with correctness and resource contracts varying by algorithm.
Structural Core vs. Domain Accent¶
The skeletal relation is controlled internal variation plus a quantified distribution of outcomes. No strict live prime for that broader relation has been verified; whether it merits one is a future admission question, not a current edge. The domain-bound mechanism is executable algorithm steps, discrete random choices, correctness conditions and complexity bounds. Randomized Algorithm is not a prime abstraction because removing computation and the fixed-input guarantee leaves a much looser motif of chance, unable to distinguish it from random inputs or stochastic measurement.
Instantiates / Related Primes¶
This entry is a kind of Algorithm.
Algorithm is the strict genus of this finite randomized procedure. “Las Vegas” and “Monte Carlo” name algorithmic contract families, not additional parent edges.
Relationships to Other Abstractions¶
Current abstraction Randomized Algorithm Domain-specific
Parents (1) — more general patterns this builds on
-
Randomized Algorithm is a kind of Algorithm Prime
A randomized algorithm is an algorithm whose internal random choices affect fixed-input behavior.A randomized algorithm remains a finite executable procedure, with internal random choices as its differentia; deterministic algorithms instantiate the broader Algorithm genus without it.
Hierarchy paths (2) — routes to 2 parentless roots
- Randomized Algorithm → Algorithm → Function (Mapping)
Neighborhood in Abstraction Space¶
Randomized Algorithm sits in a sparse region of the domain-specific corpus (79th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Storage & Lookup Data Structures (21 abstractions)
Nearest neighbors
- Computational hardness assumption — 0.83
- Sequence number — 0.83
- GI-complete — 0.82
- Bloom Filter — 0.82
- GI (complexity) — 0.82
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
Random-input average-case analysis changes the input distribution, not necessarily the algorithm. A pseudorandom implementation requires an explicit seed model. Nondeterministic computation is a distinct formal resource, not a synonym for sampling coins. Repetition can amplify a suitable Monte Carlo procedure, but does not rescue an unstated or systematically biased failure model.
References¶
[1] MIT 6.046J, Lecture 6: Randomized Algorithms, randomized-quicksort and basic quicksort slides. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j
[2] David Karger, MIT 6.856J, Lecture 1 notes: Quick Sort and MinCut. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g
[3] MIT 6.856J, worked contraction-probability solution. registry ↩a ↩b ↩c ↩d ↩e ↩f