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 makes internal random choices that affect its execution. Its expected-cost or success guarantee is taken over these choices for each fixed input, not merely over a random collection of inputs. Random-pivot quicksort is always correct but has random cost; one run of random min-cut contraction has a bounded chance of finding an optimum.[ref-219b71f5a82d][ref-b4aab3126ec0]
Scope of Application¶
In quicksort, pivot choices change recursion shape while expected running time remains \(O(n\log n)\) on every input array. In graph min-cut, avoiding edges of a fixed minimum cut during random contractions preserves that cut, and repeated independent runs raise the chance of finding an optimum.[ref-219b71f5a82d][ref-d5ba5db46089]
Clarity¶
Ask what is fixed, what is sampled and what is guaranteed. Deterministic code measured on random inputs is not thereby a randomized algorithm. A fixed pseudorandom seed yields a deterministic run unless a seed distribution or computational model is declared.
Manages Complexity¶
Probability bounds summarize many possible traces without promising that each trace is fast or successful. Las Vegas and Monte Carlo describe alternative correctness/time contracts, not two mandatory features of every algorithm.
Abstract Reasoning¶
On [1,2,3,4], pivot 2 gives balanced-enough subproblems, while repeated extreme pivots give a long chain; both sort correctly. In a four-vertex multigraph with two parallel edges within each pair and a single bridge between pairs, preserving the unique minimum cut requires avoiding the bridge through both contractions, with probability (4/5)×(2/3)=8/15. These tiny traces reveal the mechanism but do not replace general proofs.[ref-219b71f5a82d][ref-d5ba5db46089]
Knowledge Transfer¶
Sorting and min-cut share fixed input, internal sampling, choice-dependent execution and a per-input probability contract. Their actual bounds and failure conditions require separate proofs. The live Algorithm prime is the strict genus; internal random choice specializes a finite executable procedure.
[^ref-219b71f5a82d]: MIT 6.046J, Randomized Algorithms lecture. [^ref-b4aab3126ec0]: Karger, MIT 6.856J, Lecture 1. [^ref-d5ba5db46089]: MIT 6.856J, contraction-probability solution.
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.
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