On this page

Randomized Algorithms

A randomized algorithm flips coins while it runs, and lets the coins decide what to do next: which pivot to partition around, which edge to contract, which item to keep. That sounds like giving up control. In practice it is one of the most powerful moves in algorithm design. A random choice cannot be predicted by whoever built the input, so no input is "bad" any more — only some coin flips are, and those are rare. Randomization also lets you check a matrix product in instead of , pick a fair sample from a stream you cannot store, and find a minimum cut with a ten-line program.

This is the Module 5 lesson on randomized algorithms in DSA: Zero to Mastery. It assumes the quicksort lesson (Quick Sort), basic probability (expectation, independence — Probability for Engineers covers all of it), and Hash Tables. Every probability on this page was checked by an exact calculation or a simulation script, and the tables show the script's numbers.

Why this exists

Deterministic algorithms have a weakness: for each one, some input makes it slow, and an adversary who knows the code can find that input. Quicksort with "first element as pivot" takes comparisons on already-sorted data — 499,500 for , versus about 11,000 with a random pivot (our simulation). Hash tables with a fixed hash function can be flooded with colliding keys. Randomization moves the "bad case" from the input, which an adversary controls, to the coins, which nobody controls.

The second reason is that some problems have randomized algorithms far simpler or faster than any known deterministic one. In 1976 Michael Rabin and Gary Miller gave a fast randomized primality test; a deterministic polynomial-time test (AKS) did not arrive until 2002, and it is still slower in practice. Rūsiņš Freivalds (1977) showed how to verify a matrix product in time per trial. David Karger (1993) found a minimum cut by contracting random edges. Reservoir sampling, Fisher–Yates shuffling, skip lists, treaps, Bloom filters and HyperLogLog are all built on coins.

The third reason is practical: systems are full of randomness on purpose. Raft picks random election timeouts so that two nodes rarely time out together; retries add random jitter so clients do not stampede; load balancers pick two random servers and send to the less loaded. Understanding how to reason about "probably fast" and "probably correct" is part of building those systems.

Pattern triggers

If the problem says or has…Think of…
"shuffle", "random permutation", "every order equally likely"Fisher–Yates (and never the naive swap-with-anything loop)
"pick items uniformly from a stream / linked list of unknown length"Reservoir sampling (Algorithm R; Algorithm L for very long streams)
"random pick with weight"Prefix sums + binary search, or the alias method
"generate rand10 from rand7", "uniform point in a circle"Rejection sampling (a Las Vegas loop)
"-th largest", "median" with tight expected timeRandomized quickselect
Sorting where adversarial or sorted input is likelyRandom pivot (or introsort)
Hash map on untrusted keys; Codeforces hacks on unordered_mapRandomized (keyed) hashing
"global minimum cut", "fewest edges to disconnect"Karger / Karger–Stein (or Stoer–Wagner deterministically)
"verify ", "check an identity of big objects"Freivalds / polynomial identity testing by random evaluation
"is this 64-bit number prime?"Miller–Rabin
"find an element that appears in more than half / a fixed fraction"Pick random elements and check — each pick hits with constant probability
"ordered set with simple code"Treap or skip list
Answer is hard to compute but easy to verifyGuess randomly, verify, repeat (Monte Carlo → Las Vegas)

The meta-trigger: a random choice is "good" with some constant probability, and you can either repeat it cheaply or check whether it was good.

Intuition & first principles

Coins inside the algorithm, not inside the input

There are two different things people mean by "random" in algorithms:

  1. Average-case analysis: the algorithm is deterministic, and we assume the input is random (for example, "quicksort with first-element pivot is fast on random arrays"). If the input is not random — sorted, or chosen by an attacker — the guarantee disappears.
  2. Randomized algorithms: the input is anything at all, even the worst possible; the algorithm itself draws random numbers. The guarantee is "for every input, the expected cost over the algorithm's coins is small".

This lesson is about the second kind. The difference matters: a randomized algorithm's guarantee holds for sorted arrays, for attacker-crafted arrays, for everything — as long as the attacker cannot see or predict the coins (that last condition is where real systems fail; see Seeding and PRNG pitfalls).

A tiny example: find an "a"

An array of 100 letters is half a and half b, in some unknown order. Find the position of any a.

  • Deterministic scan: check positions 0, 1, 2, …. An adversary who knows you scan left to right puts all 50 bs first: 51 probes.
  • Randomized probe: look at a uniformly random position; if it is a b, try again. Each probe succeeds with probability 1/2, whatever the arrangement. The number of probes is geometric: expected , and the chance of needing more than 20 probes is .

Our simulation (200,000 runs) averaged 1.996 probes; the worst run needed 18. No arrangement of the letters changes this.

Las Vegas and Monte Carlo

The randomized probe always returns a correct answer; only its running time is random. That is one of two families:

Las VegasMonte Carlo
Answeralways correctcorrect with probability at least
Running timerandom (we bound its expectation, or its tail)bounded by a fixed function of
Examplesrandomized quicksort and quickselect, treaps, skip lists, rejection sampling, the "find an a" probeKarger's min-cut, Freivalds' check, Miller–Rabin, Bloom filters
How to make it betternothing to fix; analyse the tailrepeat independent runs: error drops exponentially

Many Monte Carlo algorithms have one-sided error: one of their answers is always trustworthy. Freivalds' "the product is wrong" is always right (it found a witness). Miller–Rabin's "composite" is always right. Karger never reports a cut smaller than the minimum, because whatever it returns is an actual cut; it can only report one that is too big.

You can convert between the two:

  • Las Vegas → Monte Carlo. Run the Las Vegas algorithm for twice its expected time and give up if it has not finished. By Markov's inequality ( for a non-negative ), it fails to finish with probability at most 1/2. Repeat to shrink that.
  • Monte Carlo → Las Vegas. Possible only if you can verify an answer: run, check, and repeat until the check passes. Expected number of rounds is .

(Complexity theorists call problems with polynomial expected-time Las Vegas algorithms ZPP, with one-sided-error Monte Carlo algorithms RP, and with two-sided error BPP. You will not need the names in interviews; the ideas above are what matter.)

Expected time versus "with high probability"

"Randomized quicksort takes expected time" is a statement about an average over coin flips. It does not rule out an occasional slow run. A stronger guarantee is with high probability (w.h.p.): the bound holds except with probability at most for some constant . Randomized quicksort has this too: it makes comparisons with probability at least (see Motwani and Raghavan, ch. 1 and 4, via Chernoff bounds). For a system with millions of calls per day, the tail matters as much as the mean: an expected- hash lookup with a heavy tail can still cause p99 latency spikes.

The five tools you need

Almost every analysis on this page uses only these:

  1. Linearity of expectation. , always — even if and are dependent. This is the workhorse.
  2. Indicator variables. if event happens, else 0. Then , and a count is a sum of indicators.
  3. Geometric trials. If each try succeeds independently with probability , the expected number of tries is .
  4. Repetition. If one run fails with probability at most , then independent runs all fail with probability . To push failure below , use runs.
  5. Union bound. — no independence needed.

Mechanics

1. Randomized quicksort: about comparisons, for every input

Quicksort picks a pivot, partitions the array into "smaller" and "larger", and recurses. Randomized quicksort picks the pivot uniformly at random from the current subarray. We count comparisons between elements, with the convention that partitioning elements compares the pivot with the other .

The derivation (indicator variables). Name the elements in sorted order (assume distinct). Let if and are ever compared. Two elements are compared at most once (only against a pivot, and a pivot is never in a later subproblem), so the total is .

When are and compared? Look at the block , which has elements. Until some element of the block is chosen as a pivot, the whole block travels together into the same subarray. The first pivot chosen from the block decides everything:

  • if it is or , the two are compared (the pivot is compared with everything in its subarray);
  • if it is anything strictly between them, they go to different sides and are never compared.

Each of the block elements is equally likely to be first, so . By linearity of expectation:

The exact value is , where . In base-2 terms, . The full proof with the exact sum, and swap counts, is in Quick Sort.

Our simulation sorted already-sorted arrays (the worst input for a first-element pivot) with a random pivot:

Exact Simulated mean (runs)Leading term First-element pivot on sorted input
1024.424.5 (200)46.145
100647.9646.8 (200)921.04,950
1,00010,985.910,902.6 (200)13,815.5499,500
10,000155,771.7157,706.6 (30)184,206.849,995,000

Two lessons. First, the exact formula matches the simulation within sampling noise; the leading term overestimates noticeably for practical because of the correction. Second, the sorted input that destroys the deterministic version is completely ordinary for the randomized one — that is the point.

2. Random pivots against adversarial inputs

Why can't an adversary build a bad input for randomized quicksort? Because the analysis above never looked at the input. The probability depends only on ranks, which every input has. For any fixed input, the expected cost is the same .

There are three ways this guarantee breaks in practice, and they are worth knowing:

  1. The adversary can see or predict the coins. If the pivot comes from a PRNG seeded with a known constant, the attacker can simulate your sort and build an input that makes every pivot bad. This is how Codeforces "hacks" work against solutions that use mt19937 rng(12345).
  2. The adversary adapts. M. Douglas McIlroy's "A Killer Adversary for Quicksort" (1999) shows a comparison function that decides element values lazily, during the sort, forcing quadratic time on almost any deterministic quicksort. It works because the "input" is chosen in response to the algorithm's comparisons.
  3. Many equal keys. With two-way partitioning, an array of all-equal keys can still be quadratic whatever the pivot. Three-way partitioning fixes that (see Quick Sort).

Production libraries mostly avoid a random seed here: C++ std::sort (introsort) and the pattern-defeating quicksorts in Go and Rust choose pivots deterministically and fall back to heapsort when recursion gets too deep, which caps the worst case at . Randomness and worst-case fallbacks solve the same problem in different ways; randomness is simpler to write in an interview.

3. Randomized quickselect: expected

To find the -th smallest element, partition around a random pivot and recurse into only the side that contains rank .

A simple bound. Call a pivot good if it lands in the middle half of the current subarray (ranks between 25% and 75%). A good pivot happens with probability 1/2, and after a good pivot the side we keep has at most of the elements. Group the run into phases: phase lasts while the subarray size is between and . Each partition in phase costs at most comparisons, and the expected number of partitions until a good pivot ends the phase is at most 2. So

The true constant is smaller. For the median, Knuth computed the expected comparisons as about . Our simulation agrees:

RunsMean comparisons Worst run
1,0012003.347.88
10,0012003.285.62
100,001403.416.85

The worst-case is still (every pivot the largest), but with probability that shrinks exponentially. For a deterministic guarantee use median of medians; both are covered in Quickselect & Order Statistics.

4. The Fisher–Yates shuffle

Goal: rearrange an array so that each of the orders has probability exactly .

Algorithm (Durstenfeld's in-place version, 1964; the idea is Fisher and Yates, 1938):

for i from n-1 down to 1:
    j = uniform random integer with 0 <= j <= i
    swap a[i], a[j]

Think of it as drawing cards from a hat. Position gets a uniformly random card from all ; then position gets a uniformly random card from the that remain; and so on. The part of the array to the right of is the "already dealt" pile, the part up to is the hat.

Trace on [A, B, C, D] with one particular run of coins:

Choices for Drawn SwapArray afterProbability of this draw
30..31a[3] ↔ a[1]A D C B1/4
20..22none (self-swap)A D C B1/3
10..10a[1] ↔ a[0]D A C B1/2

This run produces D A C B with probability .

Proof of uniformity. There are equally likely sequences of draws. Different sequences give different permutations: from the final array you can read back the draws (the element at position tells you at step , undo that swap, and repeat). So the map from draw sequences to permutations is a bijection, and every permutation has probability exactly .

flowchart LR
    H["hat: positions 0..i"] -->|"pick j uniformly in 0..i"| S["swap a[i] and a[j]"]
    S --> D["position i is now final"]
    D -->|"i = i - 1"| H

The loop uses random numbers and time; it is what Python's random.shuffle, Java's Collections.shuffle and C++'s std::shuffle implement.

5. The classic biased-shuffle bug

Here is the version almost everyone writes the first time:

for i from 0 to n-1:
    j = uniform random integer with 0 <= j <= n-1     # BUG: should be i..n-1 or 0..i
    swap a[i], a[j]

It looks more random — every element gets swapped with anything. It is wrong. The loop makes draws with choices each, so there are equally likely runs. Each permutation receives a whole number of runs, so it has probability . For uniformity, would have to be divisible by . For : 27 runs over 6 permutations — 27/6 is not an integer, so some permutations must be more likely than others.

Exact counts, by enumerating all runs:

ResultRunsExact probabilitySimulated naive (600,000 trials)Simulated Fisher–Yates
0 1 244/27 = 0.14810.14830.1665
0 2 155/27 = 0.18520.18490.1669
1 0 255/27 = 0.18520.18590.1670
1 2 055/27 = 0.18520.18560.1669
2 0 144/27 = 0.14810.14790.1664
2 1 044/27 = 0.14810.14730.1663

Uniform would be . The naive shuffle produces three orders 25% more often than the other three. For it gets worse: across the runs, the most likely permutation gets 15 runs and the least likely 8, almost a factor of two, where uniform would be each.

A second classic bug is sorting with a random comparator, such as arr.sort(() => Math.random() - 0.5) in JavaScript. A comparison sort assumes the comparator is consistent; a random one produces a bias that depends on the sorting algorithm. With Python's sort and a coin-flip comparator, our simulation put the first element back in position 0 about 32% of the time for (uniform: 20%). This bug made the news in 2010, when the browser-choice ballot Microsoft showed EU Windows users was reported to use exactly this pattern, producing visibly unequal positions for the five browsers (Rob Weir's analysis, "Doing the Microsoft Shuffle", February 2010).

Use the library shuffle

random.shuffle, Collections.shuffle, std::shuffle and the code in this lesson are correct. If you write your own, the loop bound is j in 0..i (counting down) or i..n-1 (counting up) — never 0..n-1. In TypeScript, write Fisher–Yates; do not sort with a random comparator.

6. Reservoir sampling

Goal: read a stream of unknown length once, with memory for only items, and end with a uniformly random -subset — every item in the final sample with probability .

Algorithm R (credited to Alan Waterman in Knuth, TAOCP Vol. 2, §3.4.2; analysed by Vitter, 1985):

  1. Put the first items in the reservoir.
  2. For item number (counting from 1) with : draw uniformly in . If , replace reservoir slot with the new item; otherwise discard the new item.

So item enters with probability , and when it enters it evicts a uniformly random current member.

Trace with over items :

ItemEnter probability Drawn (range)ActionReservoir after
——fill
——fill
2/31 (0..2)replace slot 1
2/43 (0..3)discard
2/50 (0..4)replace slot 0
2/64 (0..5)discard

Proof of uniformity (induction). Claim: after items, each of them is in the reservoir with probability . For it is certain. Step to : the new item enters with probability — correct. An old item was present with probability (induction) and survives unless the new item enters and picks its slot, which happens with probability . So it is present with probability . (The same argument, applied to whole subsets, shows every -subset is equally likely.)

Simulation: choosing of the stream 100,000 times, each item was chosen between 29,652 and 30,338 times (expected 30,000).

Algorithm L (Kim-Hung Li, 1994). Algorithm R draws a random number for every item. When , almost all of those draws say "discard". Algorithm L instead computes, with one random number, how many items to skip before the next replacement (the skip length has a geometric distribution whose parameter shrinks as the stream goes on). It makes random draws in expectation instead of , which matters when the stream is huge and generating randomness is expensive. Our Python implementation of Algorithm L gave the same uniform counts as Algorithm R.

Weighted sampling. To sample with probability proportional to weights from a stream, give item the key for a uniform and keep the largest keys in a heap (Efraimidis and Spirakis, 2006). Distributed sampling uses the same trick: each machine keeps its top- keys, and merging is just "top of the union".

7. Randomness inside hashing

A hash table is fast when keys spread evenly across buckets. With a fixed hash function, someone who knows the function can send keys that all collide, turning operations into — the hash-flooding attacks described in Hash Tables.

Universal hashing (Carter and Wegman, 1979) fixes this the same way random pivots fix quicksort: pick the hash function at random from a family when the table is created. A family is universal if for any two distinct keys ,

where is the number of buckets. The classic family: choose a prime larger than every key, pick random and , and set . With chaining, the expected length of the chain a lookup scans is at most for any fixed set of keys (CLRS, Theorem 11.3 in the 3rd edition) — linearity of expectation over the indicator "key collides with key " again.

In practice:

  • Languages use keyed hashes (SipHash with a per-process random key in Python, Rust and Ruby). The key plays the role of the random choice of .
  • In competitive programming, C++ unordered_map<long long, …> uses the identity hash and predictable bucket counts, so problem setters add anti-hash tests that make it quadratic. The fix is a mixing function (splitmix64) with a seed taken from the clock at run time; code is in Hash Tables.
  • Polynomial string hashing needs a random base for the same reason; see String Hashing.

8. Karger's minimum cut

A cut of a connected undirected graph splits the vertices into two non-empty groups; its size is the number of edges crossing between them. The global minimum cut is the smallest such number — the fewest links whose failure disconnects the network.

Contraction. To contract an edge , merge and into one super-vertex, keep all their other edges (parallel edges are allowed and matter), and delete the edges between and (they would be self-loops).

Karger's algorithm (1993): while more than two super-vertices remain, contract a uniformly random remaining edge. When two are left, the edges between them form a cut. Return its size.

Run it on two triangles joined by a bridge: triangle , triangle , and the bridge –. Seven edges; the minimum cut is 1 (the bridge).

A successful run (it never picks the bridge):

StepContractSuper-verticesEdges left (parallel edges counted)
0—A, B, C, D, E, F7
1A–BAB, C, D, E, F6: AB–C ×2, C–D, D–E, E–F, D–F
2AB–CABC, D, E, F4: C–D, D–E, E–F, D–F
3D–EABC, DE, F3: ABC–DE, DE–F ×2
4DE–FABC, DEF1: the bridge. Cut found = 1 ✔

A failing run (it contracts the bridge first, probability 1/7):

StepContractSuper-verticesEdges left
1C–DA, B, CD, E, F6
2A–BAB, CD, E, F5: AB–CD ×2, CD–E, CD–F, E–F
3E–FAB, CD, EF4: AB–CD ×2, CD–EF ×2
4AB–CDABCD, EF2. Cut found = 2 ✘ (not minimum)

An exact calculation over all contraction orders gives a success probability of for this graph.

Why one run succeeds with probability at least . Fix one minimum cut with edges. The run returns exactly when it never contracts an edge of .

  1. Every vertex has degree at least (otherwise cutting that vertex off would be a smaller cut). So the graph has edges, and the first random edge is in with probability .
  2. The same holds later: after contractions there are super-vertices, each still of degree (a super-vertex's edges form a cut of the original graph), so at least edges remain, and the next pick hits with probability at most .
  3. Multiply the survival probabilities over the contractions:

(The product telescopes: numerators cancel against denominators .)

A bonus corollary: since each minimum cut is found with probability at least , and the events "run returns cut " are disjoint, a graph has at most minimum cuts. The cycle achieves this: any two of its edges form a minimum cut. In our simulation on , each of the 15 minimum cuts was returned in about of runs (the cut vs : 0.068), so the bound is tight.

Amplification. One run succeeds with probability , which is small. Run it times and keep the smallest cut. All runs fail with probability at most . Choosing pushes the failure probability below :

GraphBound True (exact / simulated)Runs for Runs for
Two triangles + bridge61/15 = 0.06713/35 = 0.371 (exact)70208
Two + 2 edges81/28 = 0.0360.2159 exact, 0.2163 simulated129387

The bound is pessimistic for these graphs, which is typical; the guarantee is what lets you choose without knowing the true . In 2,000 repetitions of "129 runs, take the minimum" on the pair, every repetition found the true minimum cut of 2.

Cost. One run is with the union-find trick in the code below (shuffle the edges once and contract them in that order, skipping edges whose ends are already merged — this is equivalent to repeatedly picking a uniformly random remaining non-loop edge). runs give an overall for high-probability success. Karger–Stein (1996) observes that early contractions are safe and late ones are risky, so it contracts to about vertices, then recurses twice; this gives total for a w.h.p. answer. Deterministic alternatives: Stoer–Wagner in , or max-flow computations (Network Flow).

flowchart TD
    G["graph with n vertices"] --> P["pick a uniformly random edge"]
    P --> C["contract it, drop self-loops"]
    C --> Q{"more than 2 super-vertices?"}
    Q -->|"yes"| P
    Q -->|"no"| R["edges between the 2 super-vertices = a cut"]
    R --> M["repeat T times, keep the smallest"]

9. Freivalds' matrix-product check

Problem. Someone hands you matrices , and a claimed product . Is ? Recomputing costs (or with the best known theory, impractical).

Freivalds (1977): pick a random vector . Compute and — three matrix-vector products, . If they differ, for certain. If they agree, say "probably equal". Repeat times.

Why a wrong is caught with probability at least 1/2. Let , so some entry . The test passes only if , in particular only if :

Condition on all coordinates of except ; then is a fixed number. The equation has at most one solution for , and is 0 or 1 with probability 1/2 each. So . After independent rounds, a wrong product survives with probability at most : about one in a million for . A correct product is never rejected (one-sided error).

Worked example. , , so . The claimed is wrong in one entry.

Verdict
(0, 0)(0, 0)(0, 0)(0, 0)pass (fooled)
(1, 0)(1, 1)(5, 7)(5, 7)pass (fooled)
(0, 1)(0, 2)(6, 8)(6, 9)reject
(1, 1)(1, 3)(11, 15)(11, 16)reject

Exactly half of the four vectors expose the error — the bound is tight for a single wrong entry. Simulation agrees: with one wrong entry in a product, one round accepted in 49.9% of 200,000 trials. If every diagonal entry is wrong (), a round passes only when : probability ; simulated 0.0157. More errors make detection easier, never harder.

Freivalds is a special case of polynomial identity testing: to check whether two big expressions are equal, evaluate both at a random point. The Schwartz–Zippel lemma bounds the error: a nonzero polynomial of degree vanishes at a random point of a set with probability at most . Random-base string hashing is the same idea (two different strings are two different polynomials).

10. Miller–Rabin, in one paragraph

Fermat's little theorem says for prime . Miller–Rabin strengthens the test: write with odd; for a prime, the sequence either starts at 1 or hits somewhere. A base that breaks this pattern is a witness that is composite (a certain answer). Rabin (1980) proved that for odd composite at least 3/4 of bases are witnesses, so random bases miss with probability at most . For 64-bit integers no randomness is needed: the fixed bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 are known to give a deterministic test for all — far beyond .

Correction

An earlier version said these twelve bases are deterministic below . That bound belongs to the thirteen bases . The smallest composite that fools all twelve bases is (it is caught by base 41); see OEIS A014233. The conclusion for 64-bit integers is unchanged.

The full algorithm, modular exponentiation and Pollard's rho are in Advanced Number Theory.

11. Randomized data structures

The same "coins instead of bookkeeping" idea gives several data structures, covered in their own lessons:

  • Treaps: a BST where each node also gets a random priority, kept in heap order. The shape equals a BST built by inserting keys in random order, so the expected depth is — the same indicator-variable proof as quicksort. See Treaps, Splay Trees & Skip Lists.
  • Skip lists (Pugh, 1990): a sorted linked list where each node is promoted to the next "express lane" with probability 1/2. Expected search; Redis sorted sets and LevelDB/RocksDB memtables use them (same lesson).
  • Bloom filters, Count-Min sketches, HyperLogLog: Monte Carlo data structures that trade a small, tunable error for huge memory savings. See Probabilistic Data Structures and Bloom Filters.

The ladder: brute force → better → optimal

Two problems where randomness changes the complexity class of what is practical.

Verifying a matrix product

RungMethodTimeErrorWhy it is better than the rung above
1Recompute naively, comparenoneBaseline
2Recompute with StrassennoneFewer multiplications, but large constants and numerical issues
3Freivalds, rounds, one-sidedVerification is cheaper than computation; for , : about operations instead of

Global minimum cut

RungMethodTimeErrorWhy it is better
1Try all splitsnoneObviously correct; test oracle for
2Fix vertex ; max-flow from to every other max-flowsnonePolynomial; the min cut separates from some
3Karger, runsTen lines of code; no flow machinery
4Karger–SteinRe-uses the safe early contractions; near-quadratic
sideStoer–Wagner (deterministic)noneNo randomness; the usual library choice

For interviews, rung 3 is the expected answer to "how would you find a global min cut quickly and simply"; for production, Stoer–Wagner or Karger–Stein.

Correctness

The proofs are in the mechanics sections; here they are classified, so you can reproduce the right kind of argument for a new algorithm.

AlgorithmTypeWhat is provedTechnique
Randomized quicksortLas Vegasalways sorts; for every inputcorrectness as in deterministic quicksort; cost by indicators + linearity
Randomized quickselectLas Vegasalways correct; phases + geometric number of tries per phase
Fisher–Yatesexact samplerevery permutation has probability bijection between draw sequences and permutations
Reservoir (Algorithm R)exact samplerevery item kept with probability induction over the stream
Universal hashingLas Vegas (data structure)expected chain length for any key setindicators over pairwise collisions
KargerMonte Carlo, one-sideda given min cut survives with probability chain of conditional probabilities, degree bound
FreivaldsMonte Carlo, one-sidedwrong passes with probability per roundone free coordinate decides
Miller–RabinMonte Carlo, one-sidedcomposite passes with probability per basenumber theory (Rabin, 1980)

Two cautions apply to every row:

  • The probability is over the algorithm's random choices, for a fixed input. It says nothing if the "random" numbers are predictable to whoever chose the input.
  • Repeated runs must use independent randomness. Re-seeding with the same seed before each run repeats the same run, and the amplification disappears.

Complexity

AlgorithmTimeSpaceRandom numbers usedNotes
Randomized quicksort expected and w.h.p.; worst stack (recurse on smaller side) at most~ comparisons
Randomized quickselect expected; worst iterative expected~ comparisons for the median
Fisher–Yates in placeneeds unbiased bounded integers
Reservoir, Algorithm Rone pass, unknown
Reservoir, Algorithm L to read, expected workskips ahead in seekable streams
Universal hashing expected per operation per table
Karger, one run with union-find (shuffle)success
Karger, amplifiedfailure
Karger–Stein for w.h.p.
Freivalds, rounds bitserror
Miller–Rabin, bases bit operations (schoolbook multiplication) words for 64-bitdeterministic for 64-bit with 12 fixed bases

Implementation

Two programs per language. Each is complete, seeds its generator so that runs are reproducible, and asserts the results from this lesson. The statistical checks use tolerances of several standard deviations (for example, 60,000 shuffles of three elements: expected 10,000 per order, standard deviation about 91, accepted range 9,000–11,000).

Fisher–Yates, the biased shuffle, and reservoir sampling

import random
from collections import Counter
from typing import Iterable, List, TypeVar

T = TypeVar("T")


def fisher_yates(a: List[T], rng: random.Random) -> None:
    """Uniform in-place shuffle: every one of the n! orders has probability 1/n!."""
    for i in range(len(a) - 1, 0, -1):
        j = rng.randrange(i + 1)          # 0 <= j <= i  (i inclusive!)
        a[i], a[j] = a[j], a[i]


def naive_shuffle(a: List[T], rng: random.Random) -> None:
    """THE BUG: j ranges over the whole array. n^n equally likely runs, not divisible by n!."""
    n = len(a)
    for i in range(n):
        j = rng.randrange(n)
        a[i], a[j] = a[j], a[i]


def reservoir_sample(stream: Iterable[T], k: int, rng: random.Random) -> List[T]:
    """Algorithm R: a uniform k-subset of a stream of unknown length, O(k) memory."""
    sample: List[T] = []
    for i, x in enumerate(stream):        # x is item number i+1
        if i < k:
            sample.append(x)
        else:
            j = rng.randrange(i + 1)      # keep x with probability k/(i+1)
            if j < k:
                sample[j] = x             # it evicts a uniformly random current member
    return sample


if __name__ == "__main__":
    rng = random.Random(42)

    a = list(range(10))
    fisher_yates(a, rng)
    assert sorted(a) == list(range(10))

    trials = 60_000
    fy = Counter()
    for _ in range(trials):
        b = [0, 1, 2]
        fisher_yates(b, rng)
        fy[tuple(b)] += 1
    assert len(fy) == 6 and all(9_000 <= c <= 11_000 for c in fy.values())

    nv = Counter()
    for _ in range(27_000):
        b = [0, 1, 2]
        naive_shuffle(b, rng)
        nv[tuple(b)] += 1
    print("naive: (1,0,2) ->", nv[(1, 0, 2)], " (0,1,2) ->", nv[(0, 1, 2)], " (exact 5000 vs 4000)")
    assert nv[(1, 0, 2)] > 1.15 * nv[(0, 1, 2)]

    hits = Counter()
    for _ in range(30_000):
        hits.update(reservoir_sample(range(10), 3, rng))
    assert all(8_400 <= hits[x] <= 9_600 for x in range(10))   # expected 9000 each
    assert reservoir_sample([7, 8], 5, rng) == [7, 8]           # short stream: keep all
    print("fisher-yates, naive-shuffle demo, reservoir sampling: all tests passed")
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.stream.IntStream;

public class Main {
    /** Uniform in-place shuffle: every one of the n! orders has probability 1/n!. */
    static void fisherYates(int[] a, Random rng) {
        for (int i = a.length - 1; i > 0; i--) {
            int j = rng.nextInt(i + 1);              // 0 <= j <= i
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }

    /** THE BUG: j ranges over the whole array, giving n^n equally likely runs. */
    static void naiveShuffle(int[] a, Random rng) {
        for (int i = 0; i < a.length; i++) {
            int j = rng.nextInt(a.length);
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }

    /** Algorithm R: uniform k-subset of a stream of unknown length. */
    static <T> List<T> reservoirSample(Iterator<T> stream, int k, Random rng) {
        List<T> sample = new ArrayList<>(k);
        long i = 0;
        while (stream.hasNext()) {
            T x = stream.next();
            if (i < k) {
                sample.add(x);
            } else {
                long j = rng.nextLong(i + 1);       // keep x with probability k/(i+1)
                if (j < k) sample.set((int) j, x);
            }
            i++;
        }
        return sample;
    }

    static String key(int[] a) {
        StringBuilder sb = new StringBuilder();
        for (int x : a) sb.append(x);
        return sb.toString();
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        Random rng = new Random(42);

        int[] a = IntStream.range(0, 10).toArray();
        fisherYates(a, rng);
        check(IntStream.of(a).sorted().boxed().toList().equals(IntStream.range(0, 10).boxed().toList()), "permutation");

        Map<String, Integer> fy = new HashMap<>();
        for (int t = 0; t < 60_000; t++) {
            int[] b = {0, 1, 2};
            fisherYates(b, rng);
            fy.merge(key(b), 1, Integer::sum);
        }
        check(fy.size() == 6, "six orders");
        for (int c : fy.values()) check(c >= 9_000 && c <= 11_000, "uniform");

        Map<String, Integer> nv = new HashMap<>();
        for (int t = 0; t < 27_000; t++) {
            int[] b = {0, 1, 2};
            naiveShuffle(b, rng);
            nv.merge(key(b), 1, Integer::sum);
        }
        System.out.println("naive: (1,0,2) -> " + nv.get("102") + "  (0,1,2) -> " + nv.get("012") + "  (exact 5000 vs 4000)");
        check(nv.get("102") > 1.15 * nv.get("012"), "naive is biased");

        int[] hits = new int[10];
        for (int t = 0; t < 30_000; t++) {
            for (int x : reservoirSample(IntStream.range(0, 10).iterator(), 3, rng)) hits[x]++;
        }
        for (int h : hits) check(h >= 8_400 && h <= 9_600, "reservoir uniform");
        check(reservoirSample(List.of(7, 8).iterator(), 5, rng).equals(List.of(7, 8)), "short stream");
        System.out.println("fisher-yates, naive-shuffle demo, reservoir sampling: all tests passed");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <random>
#include <utility>
#include <vector>
using namespace std;

// Uniform in-place shuffle: every one of the n! orders has probability 1/n!.
template <class T, class RNG>
void fisherYates(vector<T>& a, RNG& rng) {
    for (size_t i = a.size(); i-- > 1;) {
        uniform_int_distribution<size_t> pick(0, i);   // 0 <= j <= i, unbiased
        swap(a[i], a[pick(rng)]);
    }
}

// THE BUG: j ranges over the whole array, giving n^n equally likely runs.
template <class T, class RNG>
void naiveShuffle(vector<T>& a, RNG& rng) {
    uniform_int_distribution<size_t> pick(0, a.size() - 1);
    for (size_t i = 0; i < a.size(); i++) swap(a[i], a[pick(rng)]);
}

// Algorithm R: uniform k-subset of a stream (here: any input range) of unknown length.
template <class It, class RNG>
vector<typename iterator_traits<It>::value_type> reservoirSample(It first, It last, size_t k, RNG& rng) {
    vector<typename iterator_traits<It>::value_type> sample;
    uint64_t i = 0;
    for (; first != last; ++first, ++i) {
        if (i < k) {
            sample.push_back(*first);
        } else {
            uniform_int_distribution<uint64_t> pick(0, i);  // keep with probability k/(i+1)
            uint64_t j = pick(rng);
            if (j < k) sample[j] = *first;
        }
    }
    return sample;
}

int main() {
    mt19937_64 rng(42);

    vector<int> a(10);
    iota(a.begin(), a.end(), 0);
    fisherYates(a, rng);
    vector<int> s = a;
    sort(s.begin(), s.end());
    for (int i = 0; i < 10; i++) assert(s[i] == i);

    map<vector<int>, int> fy;
    for (int t = 0; t < 60000; t++) {
        vector<int> b = {0, 1, 2};
        fisherYates(b, rng);
        fy[b]++;
    }
    assert(fy.size() == 6);
    for (auto& [perm, c] : fy) assert(c >= 9000 && c <= 11000);

    map<vector<int>, int> nv;
    for (int t = 0; t < 27000; t++) {
        vector<int> b = {0, 1, 2};
        naiveShuffle(b, rng);
        nv[b]++;
    }
    int biased = nv[{1, 0, 2}], plain = nv[{0, 1, 2}];
    cout << "naive: (1,0,2) -> " << biased << "  (0,1,2) -> " << plain << "  (exact 5000 vs 4000)\n";
    assert(biased > 1.15 * plain);

    vector<int> stream(10);
    iota(stream.begin(), stream.end(), 0);
    vector<int> hits(10, 0);
    for (int t = 0; t < 30000; t++)
        for (int x : reservoirSample(stream.begin(), stream.end(), 3, rng)) hits[x]++;
    for (int h : hits) assert(h >= 8400 && h <= 9600);
    vector<int> shortStream = {7, 8};
    assert((reservoirSample(shortStream.begin(), shortStream.end(), 5, rng) == vector<int>{7, 8}));
    cout << "fisher-yates, naive-shuffle demo, reservoir sampling: all tests passed\n";
}
// Seedable PRNG (mulberry32) so runs are reproducible. Math.random() cannot be seeded.
function mulberry32(seed: number): () => number {
  let s = seed >>> 0;
  return () => {
    s = (s + 0x6d2b79f5) >>> 0;
    let t = s;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; // [0, 1)
  };
}

// Integer in [0, n). Bias is at most n / 2^32: negligible for small n.
function randInt(rng: () => number, n: number): number {
  return Math.floor(rng() * n);
}

// Uniform in-place shuffle: every one of the n! orders has probability 1/n!.
function fisherYates<T>(a: T[], rng: () => number): void {
  for (let i = a.length - 1; i > 0; i--) {
    const j = randInt(rng, i + 1); // 0 <= j <= i
    [a[i], a[j]] = [a[j], a[i]];
  }
}

// THE BUG: j ranges over the whole array, giving n^n equally likely runs.
function naiveShuffle<T>(a: T[], rng: () => number): void {
  for (let i = 0; i < a.length; i++) {
    const j = randInt(rng, a.length);
    [a[i], a[j]] = [a[j], a[i]];
  }
}

// Algorithm R: uniform k-subset of a stream of unknown length.
function reservoirSample<T>(stream: Iterable<T>, k: number, rng: () => number): T[] {
  const sample: T[] = [];
  let i = 0;
  for (const x of stream) {
    if (i < k) sample.push(x);
    else {
      const j = randInt(rng, i + 1);
      if (j < k) sample[j] = x;
    }
    i++;
  }
  return sample;
}

function assert(ok: boolean, what: string): void {
  if (!ok) throw new Error("failed: " + what);
}

function* range(n: number): Generator<number> {
  for (let i = 0; i < n; i++) yield i;
}

const rng = mulberry32(42);

const a = [...range(10)];
fisherYates(a, rng);
assert([...a].sort((x, y) => x - y).join() === [...range(10)].join(), "permutation");

const fy = new Map<string, number>();
for (let t = 0; t < 60000; t++) {
  const b = [0, 1, 2];
  fisherYates(b, rng);
  fy.set(b.join(""), (fy.get(b.join("")) ?? 0) + 1);
}
assert(fy.size === 6, "six orders");
for (const c of fy.values()) assert(c >= 9000 && c <= 11000, "uniform");

const nv = new Map<string, number>();
for (let t = 0; t < 27000; t++) {
  const b = [0, 1, 2];
  naiveShuffle(b, rng);
  nv.set(b.join(""), (nv.get(b.join("")) ?? 0) + 1);
}
const biased = nv.get("102") ?? 0, plain = nv.get("012") ?? 0;
console.log(`naive: (1,0,2) -> ${biased}  (0,1,2) -> ${plain}  (exact 5000 vs 4000)`);
assert(biased > 1.15 * plain, "naive is biased");

const hits = new Array<number>(10).fill(0);
for (let t = 0; t < 30000; t++) for (const x of reservoirSample(range(10), 3, rng)) hits[x]++;
for (const h of hits) assert(h >= 8400 && h <= 9600, "reservoir uniform");
assert(reservoirSample([7, 8], 5, rng).join() === "7,8", "short stream");
console.log("fisher-yates, naive-shuffle demo, reservoir sampling: all tests passed");

Karger's min-cut (repeated) and Freivalds' check

import math
import random
from typing import List, Tuple

Edge = Tuple[int, int]


def karger_once(n: int, edges: List[Edge], rng: random.Random) -> int:
    """One contraction run: returns the size of the cut it ends with (may not be minimum)."""
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]       # path halving
            x = parent[x]
        return x

    order = edges[:]
    rng.shuffle(order)            # contracting edges in random order == picking random edges
    groups = n
    for u, v in order:
        if groups == 2:
            break
        a, b = find(u), find(v)
        if a != b:                # skip self-loops (both ends already merged)
            parent[a] = b
            groups -= 1
    return sum(1 for u, v in edges if find(u) != find(v))


def karger_min_cut(n: int, edges: List[Edge], rng: random.Random, fail_prob: float = 1e-6) -> int:
    """Repeat enough times that P(miss the min cut) <= fail_prob (graph must be connected)."""
    p = 2 / (n * (n - 1))                               # one run succeeds w.p. >= p
    trials = math.ceil(math.log(1 / fail_prob) / p)     # (1 - p)^T <= e^(-pT) <= fail_prob
    return min(karger_once(n, edges, rng) for _ in range(trials))


def freivalds(A: List[List[int]], B: List[List[int]], C: List[List[int]], rounds: int,
              rng: random.Random) -> bool:
    """False means AB != C for sure. True means AB == C with error <= 2^-rounds."""
    n = len(A)
    for _ in range(rounds):
        r = [rng.randrange(2) for _ in range(n)]
        Br = [sum(B[i][j] * r[j] for j in range(n)) for i in range(n)]
        ABr = [sum(A[i][j] * Br[j] for j in range(n)) for i in range(n)]
        Cr = [sum(C[i][j] * r[j] for j in range(n)) for i in range(n)]
        if ABr != Cr:
            return False                                 # a witness: definitely wrong
    return True


if __name__ == "__main__":
    rng = random.Random(7)

    # Two 4-cliques joined by two edges: the unique minimum cut has 2 edges.
    two_k4 = [(i, j) for base in (0, 4) for i in range(base, base + 4) for j in range(i + 1, base + 4)]
    two_k4 += [(0, 4), (1, 5)]
    assert karger_min_cut(8, two_k4, rng) == 2
    # A bridge between two triangles: minimum cut 1.
    assert karger_min_cut(6, [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5), (2, 3)], rng) == 1
    # A 6-cycle: every pair of edges is a minimum cut.
    assert karger_min_cut(6, [(i, (i + 1) % 6) for i in range(6)], rng) == 2

    A = [[2, 3, 1], [0, 1, 4], [5, 2, 2]]
    B = [[1, 0, 2], [3, 1, 0], [0, 2, 1]]
    C = [[sum(A[i][k] * B[k][j] for k in range(3)) for j in range(3)] for i in range(3)]
    assert freivalds(A, B, C, 20, rng)
    C[1][2] += 1                                         # corrupt one entry
    assert not freivalds(A, B, C, 20, rng)
    print("karger (repeated) and freivalds: all tests passed")
import java.util.Random;

public class Main {
    static int[] parent;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];    // path halving
            x = parent[x];
        }
        return x;
    }

    /** One contraction run; returns the size of the cut it ends with. */
    static int kargerOnce(int n, int[][] edges, Random rng) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int[][] order = edges.clone();
        for (int i = order.length - 1; i > 0; i--) {          // Fisher-Yates on the edges
            int j = rng.nextInt(i + 1);
            int[] t = order[i]; order[i] = order[j]; order[j] = t;
        }
        int groups = n;
        for (int[] e : order) {
            if (groups == 2) break;
            int a = find(e[0]), b = find(e[1]);
            if (a != b) { parent[a] = b; groups--; }
        }
        int cut = 0;
        for (int[] e : edges) if (find(e[0]) != find(e[1])) cut++;
        return cut;
    }

    /** Repeat so that P(miss the minimum cut) <= failProb. Graph must be connected. */
    static int kargerMinCut(int n, int[][] edges, Random rng, double failProb) {
        double p = 2.0 / ((double) n * (n - 1));
        long trials = (long) Math.ceil(Math.log(1 / failProb) / p);
        int best = Integer.MAX_VALUE;
        for (long t = 0; t < trials; t++) best = Math.min(best, kargerOnce(n, edges, rng));
        return best;
    }

    /** false: AB != C for sure. true: AB == C with error <= 2^-rounds. */
    static boolean freivalds(long[][] A, long[][] B, long[][] C, int rounds, Random rng) {
        int n = A.length;
        for (int round = 0; round < rounds; round++) {
            long[] r = new long[n];
            for (int i = 0; i < n; i++) r[i] = rng.nextInt(2);
            long[] br = mulVec(B, r), abr = mulVec(A, br), cr = mulVec(C, r);
            for (int i = 0; i < n; i++) if (abr[i] != cr[i]) return false;
        }
        return true;
    }

    static long[] mulVec(long[][] M, long[] v) {
        long[] out = new long[v.length];
        for (int i = 0; i < M.length; i++)
            for (int j = 0; j < v.length; j++) out[i] += M[i][j] * v[j];
        return out;
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        Random rng = new Random(7);

        int[][] twoK4 = new int[14][];
        int m = 0;
        for (int base = 0; base <= 4; base += 4)
            for (int i = base; i < base + 4; i++)
                for (int j = i + 1; j < base + 4; j++) twoK4[m++] = new int[] {i, j};
        twoK4[m++] = new int[] {0, 4};
        twoK4[m++] = new int[] {1, 5};
        check(kargerMinCut(8, twoK4, rng, 1e-6) == 2, "two K4");
        int[][] bridge = {{0, 1}, {1, 2}, {0, 2}, {3, 4}, {4, 5}, {3, 5}, {2, 3}};
        check(kargerMinCut(6, bridge, rng, 1e-6) == 1, "bridge");
        int[][] cycle = new int[6][];
        for (int i = 0; i < 6; i++) cycle[i] = new int[] {i, (i + 1) % 6};
        check(kargerMinCut(6, cycle, rng, 1e-6) == 2, "cycle");

        long[][] A = {{2, 3, 1}, {0, 1, 4}, {5, 2, 2}};
        long[][] B = {{1, 0, 2}, {3, 1, 0}, {0, 2, 1}};
        long[][] C = new long[3][3];
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++) C[i][j] += A[i][k] * B[k][j];
        check(freivalds(A, B, C, 20, rng), "correct product accepted");
        C[1][2] += 1;
        check(!freivalds(A, B, C, 20, rng), "wrong product rejected");
        System.out.println("karger (repeated) and freivalds: all tests passed");
    }
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <random>
#include <utility>
#include <vector>
using namespace std;
using Edge = pair<int, int>;

struct DSU {
    vector<int> p;
    explicit DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        while (p[x] != x) x = p[x] = p[p[x]];   // path halving
        return x;
    }
};

// One contraction run; returns the size of the cut it ends with.
int kargerOnce(int n, const vector<Edge>& edges, mt19937_64& rng) {
    DSU d(n);
    vector<Edge> order = edges;
    shuffle(order.begin(), order.end(), rng);   // std::shuffle is Fisher-Yates
    int groups = n;
    for (auto [u, v] : order) {
        if (groups == 2) break;
        int a = d.find(u), b = d.find(v);
        if (a != b) { d.p[a] = b; groups--; }
    }
    int cut = 0;
    for (auto [u, v] : edges) cut += d.find(u) != d.find(v);
    return cut;
}

// Repeat so that P(miss the minimum cut) <= failProb. Graph must be connected.
int kargerMinCut(int n, const vector<Edge>& edges, mt19937_64& rng, double failProb = 1e-6) {
    double p = 2.0 / (double(n) * (n - 1));
    long long trials = (long long)ceil(log(1 / failProb) / p);
    int best = INT_MAX;
    for (long long t = 0; t < trials; t++) best = min(best, kargerOnce(n, edges, rng));
    return best;
}

using Mat = vector<vector<long long>>;

vector<long long> mulVec(const Mat& M, const vector<long long>& v) {
    vector<long long> out(M.size(), 0);
    for (size_t i = 0; i < M.size(); i++)
        for (size_t j = 0; j < v.size(); j++) out[i] += M[i][j] * v[j];
    return out;
}

// false: AB != C for sure. true: AB == C with error <= 2^-rounds.
bool freivalds(const Mat& A, const Mat& B, const Mat& C, int rounds, mt19937_64& rng) {
    uniform_int_distribution<int> bit(0, 1);
    for (int round = 0; round < rounds; round++) {
        vector<long long> r(A.size());
        for (auto& x : r) x = bit(rng);
        if (mulVec(A, mulVec(B, r)) != mulVec(C, r)) return false;
    }
    return true;
}

int main() {
    mt19937_64 rng(7);

    vector<Edge> twoK4;
    for (int base : {0, 4})
        for (int i = base; i < base + 4; i++)
            for (int j = i + 1; j < base + 4; j++) twoK4.push_back({i, j});
    twoK4.push_back({0, 4});
    twoK4.push_back({1, 5});
    assert(kargerMinCut(8, twoK4, rng) == 2);
    assert(kargerMinCut(6, {{0, 1}, {1, 2}, {0, 2}, {3, 4}, {4, 5}, {3, 5}, {2, 3}}, rng) == 1);
    vector<Edge> cycle;
    for (int i = 0; i < 6; i++) cycle.push_back({i, (i + 1) % 6});
    assert(kargerMinCut(6, cycle, rng) == 2);

    Mat A = {{2, 3, 1}, {0, 1, 4}, {5, 2, 2}};
    Mat B = {{1, 0, 2}, {3, 1, 0}, {0, 2, 1}};
    Mat C(3, vector<long long>(3, 0));
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++) C[i][j] += A[i][k] * B[k][j];
    assert(freivalds(A, B, C, 20, rng));
    C[1][2] += 1;
    assert(!freivalds(A, B, C, 20, rng));
    cout << "karger (repeated) and freivalds: all tests passed\n";
}
type Edge = [number, number];

function mulberry32(seed: number): () => number {
  let s = seed >>> 0;
  return () => {
    s = (s + 0x6d2b79f5) >>> 0;
    let t = s;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

// One contraction run; returns the size of the cut it ends with.
function kargerOnce(n: number, edges: Edge[], rng: () => number): number {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };
  const order = [...edges];
  for (let i = order.length - 1; i > 0; i--) {
    const j = Math.floor(rng() * (i + 1));
    [order[i], order[j]] = [order[j], order[i]];
  }
  let groups = n;
  for (const [u, v] of order) {
    if (groups === 2) break;
    const a = find(u), b = find(v);
    if (a !== b) {
      parent[a] = b;
      groups--;
    }
  }
  return edges.filter(([u, v]) => find(u) !== find(v)).length;
}

// Repeat so that P(miss the minimum cut) <= failProb. Graph must be connected.
function kargerMinCut(n: number, edges: Edge[], rng: () => number, failProb = 1e-6): number {
  const p = 2 / (n * (n - 1));
  const trials = Math.ceil(Math.log(1 / failProb) / p);
  let best = Infinity;
  for (let t = 0; t < trials; t++) best = Math.min(best, kargerOnce(n, edges, rng));
  return best;
}

const mulVec = (M: number[][], v: number[]): number[] =>
  M.map((row) => row.reduce((s, x, j) => s + x * v[j], 0));

// false: AB != C for sure. true: AB == C with error <= 2^-rounds.
// Plain numbers are exact only up to 2^53: use BigInt for large entries.
function freivalds(A: number[][], B: number[][], C: number[][], rounds: number, rng: () => number): boolean {
  for (let round = 0; round < rounds; round++) {
    const r = A.map(() => (rng() < 0.5 ? 0 : 1));
    const abr = mulVec(A, mulVec(B, r)), cr = mulVec(C, r);
    if (abr.some((x, i) => x !== cr[i])) return false;
  }
  return true;
}

function assert(ok: boolean, what: string): void {
  if (!ok) throw new Error("failed: " + what);
}

const rng = mulberry32(7);

const twoK4: Edge[] = [];
for (const base of [0, 4])
  for (let i = base; i < base + 4; i++)
    for (let j = i + 1; j < base + 4; j++) twoK4.push([i, j]);
twoK4.push([0, 4], [1, 5]);
assert(kargerMinCut(8, twoK4, rng) === 2, "two K4");
assert(kargerMinCut(6, [[0, 1], [1, 2], [0, 2], [3, 4], [4, 5], [3, 5], [2, 3]], rng) === 1, "bridge");
const cycle: Edge[] = [0, 1, 2, 3, 4, 5].map((i) => [i, (i + 1) % 6] as Edge);
assert(kargerMinCut(6, cycle, rng) === 2, "cycle");

const A = [[2, 3, 1], [0, 1, 4], [5, 2, 2]];
const B = [[1, 0, 2], [3, 1, 0], [0, 2, 1]];
const C = A.map((row) => B[0].map((_, j) => row.reduce((s, x, k) => s + x * B[k][j], 0)));
assert(freivalds(A, B, C, 20, rng), "correct product accepted");
C[1][2] += 1;
assert(!freivalds(A, B, C, 20, rng), "wrong product rejected");
console.log("karger (repeated) and freivalds: all tests passed");

Notes on the choices:

  • Unbiased bounded integers. Python's randrange, Java's nextInt(bound)/nextLong(bound) and C++'s uniform_int_distribution are exactly uniform. The TypeScript Math.floor(rng() * n) has a bias of at most — irrelevant here, but use rejection sampling (as the libraries do) if is large or the stakes are high. Never use rand() % n in C: on implementations where RAND_MAX is 32767 (MSVC), rand() % 10000 returns each of 0–2767 with probability and each of 2768–9999 with only .
  • Seedable TypeScript generator. Math.random() cannot be seeded, which makes tests irreproducible, so the code ships a tiny mulberry32 generator. It is fine for simulations and unsuitable for anything security-related.
  • Karger via shuffled edges. Shuffling the edge list once and contracting edges in that order (skipping edges inside one group) picks, at every step, a uniformly random edge among those that are not self-loops — the same distribution as "pick a random remaining edge" — and it reuses union-find from Union-Find.
  • The number of Karger runs is computed from the bound and a target failure probability, not hard-coded. Repeated runs share one generator, so they are independent.
  • Freivalds with integers. The check is exact in integer arithmetic. With large entries, use 64-bit or modular arithmetic (work modulo a large prime and pick uniformly in ; the error per round drops to ). With floating-point matrices, exact equality is meaningless — compare with a tolerance.

Seeding and PRNG pitfalls

Every guarantee on this page assumes the random numbers are unpredictable to whoever chose the input and independent between runs. Computers produce pseudo-random numbers: a deterministic function of a seed. Most bugs in randomized code are really bugs in how the seed is chosen.

In contests

  • Fixed seed = no randomness. mt19937 rng(42) or srand(0) gives the same sequence on every run, and anyone can read your code during the hacking phase and build an input against it. Seed from a high-resolution clock: mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());.
  • srand(time(0)) changes only once per second; an attacker can try all seeds in a time window. Again, use a nanosecond clock.
  • random_device is supposed to be non-deterministic, but older MinGW builds of GCC on Windows returned the same sequence every run. Combine it with a clock to be safe.
  • rand() is weak. RAND_MAX can be 32767, so rand() % n for never produces most values; and random_shuffle (removed in C++17) used it. Use mt19937_64 with shuffle and uniform_int_distribution.
  • Anti-hash tests. unordered_map with default hashing gets hacked; see Hash Tables.
  • Reproducibility while debugging. Print the seed at the start of a stress test, so a failing case can be replayed (Testing & Debugging Algorithms).

In production

  • Statistical PRNGs are predictable. Java's java.util.Random is a 48-bit linear congruential generator: a few outputs reveal its state. V8's Math.random() (xorshift128+) and Mersenne Twister can also be reconstructed from outputs. For tokens, passwords, keys, session ids or anything an attacker benefits from guessing, use a cryptographically secure generator: secrets in Python, SecureRandom in Java, crypto.getRandomValues / crypto.randomUUID in JavaScript, /dev/urandom or getrandom() on Linux. See Cryptography & PKI.
  • Low-entropy seeds are catastrophic. In 2008 Debian discovered that a 2006 patch to its OpenSSL package had removed almost all entropy from the random generator, leaving the process id as the only variable — so only 32,767 possible keys per architecture and key type for SSH and SSL keys generated on Debian and Ubuntu over about two years (Debian Security Advisory DSA-1571, CVE-2008-0166).
  • Shuffles that cannot reach most permutations. In 1999 researchers at Reliable Software Technologies showed that a popular online poker site's shuffle had both an off-by-one bias and a generator seeded with the number of milliseconds since midnight; by syncing clocks they could predict the entire deck after seeing a few cards ("How We Learned to Cheat at Online Poker", Arkin et al., 1999). The general limit: a generator with bits of state can produce at most different shuffles. A 52-card deck has orders, so a 32-bit or 64-bit seed reaches a vanishing fraction of them. Even Mersenne Twister's states cover all orders only for (, by our computation) — a point the Python documentation for random.shuffle makes with this same number.
  • Forked workers share a stream. A process that seeds its generator and then forks gives every child the same state, so "random" augmentations or sampled jobs repeat across workers. The PyTorch documentation's section on randomness in multi-process data loading shows the standard fix (seed each worker from its id and a base seed).
  • Independence between runs. Restarting a Monte Carlo algorithm with the same seed is not a new trial. Log seeds; derive per-run seeds from a master seed with a splitter (SplittableRandom, NumPy's SeedSequence.spawn).
  • Modulo bias and float tricks. rand() % n and Math.floor(Math.random() * n) are slightly non-uniform for large ; library bounded-integer functions use rejection to be exact.

War Story (illustrative)

A team's load test "randomly" chose which of 50 cached keys each simulated user would read, using a generator created inside a request handler with new Random(System.currentTimeMillis()). Under load, hundreds of handlers ran in the same millisecond, got the same seed, and requested the same key — the test reported a 99% cache hit rate that production never saw. The fix was one shared, thread-safe generator (ThreadLocalRandom), created once.

Real-world uses

  • Hash tables in every major language use randomized (keyed) hashing to resist flooding: Python since 3.3 (hash randomization on by default; SipHash since 3.4, PEP 456), Rust's HashMap (SipHash with random keys), Ruby; Go randomizes map iteration order so programs cannot depend on it.
  • Sorted sets and memtables. Redis sorted sets (ZADD, ZRANGE) are skip lists plus a hash table; LevelDB and RocksDB keep recent writes in a skip-list memtable.
  • Load balancing: the power of two choices. Send each request to the less loaded of two randomly chosen servers. With balls into bins, one random choice gives a maximum load of about ; two choices give about (Azar, Broder, Karlin and Upfal, 1994; Mitzenmacher, 2001). NGINX exposes it as random two least_conn. See Load Balancing Algorithms.
  • Distributed systems timing. Raft uses randomized election timeouts (150–300 ms in the paper) so split votes are rare (Leader Election); retries add random jitter to exponential backoff to avoid synchronized retry storms (Timeouts, Retries & Backoff); Ethernet's classic binary exponential backoff picks a random slot count.
  • Sampling. Reservoir sampling is used for log and trace sampling and in database TABLESAMPLE-style features; weighted reservoir sampling for sampling by importance. Experiment platforms hash user ids with a salt to assign users to A/B arms (Statistics & A/B Testing).
  • Cryptography. RSA and other key generation pick random large numbers and test them with Miller–Rabin (OpenSSL's BN_is_prime_ex and its successors run multiple Miller–Rabin rounds).
  • Approximate counting and membership. Bloom filters in Bigtable/Cassandra/RocksDB read paths, HyperLogLog in Redis PFCOUNT and many analytics engines (Probabilistic Data Structures).
  • Network reliability. Karger's contraction idea underlies estimates of how likely a network is to disconnect when links fail at random.
  • Verifiable computation. Freivalds-style random checks let a weak client verify work done by a powerful server; the same random-evaluation idea underlies many modern proof systems.

Pitfalls & edge cases

  • Off-by-one in Fisher–Yates. j in 0..i inclusive. Using 0..i-1 (exclusive) gives Sattolo's algorithm, which produces only cyclic permutations (no element stays in place) — a real algorithm, but not a uniform shuffle.
  • Swap-with-anything shuffle (j in 0..n-1) and random-comparator sorts are biased. Use the library.
  • Reservoir with j drawn from the wrong range. It must be 0..i-1 for the -th item (1-based), i.e. randrange(i + 1) with 0-based i. Off by one breaks uniformity.
  • Re-seeding inside a loop. random.seed(time()) inside a loop that runs many times per clock tick repeats the same numbers.
  • Treating "expected" as "always". An expected- quickselect still has slow runs; in latency-critical code, add a fallback (introselect) or bound the work.
  • Ignoring the success probability. One Karger run is not an algorithm; it is a lottery ticket. Compute the number of repetitions from the bound.
  • Floating-point Freivalds. Exact equality fails on rounding; use integer or modular arithmetic, or a tolerance.
  • Disconnected input to Karger. The minimum cut is 0, and the union-find loop stops with more than two groups; check connectivity first (the code above assumes a connected graph).
  • Testing randomized code. Seed it so failures replay; test properties (output is a permutation, each item kept about of the time) with tolerances of several standard deviations, not exact values.
  • Using a non-cryptographic generator for secrets. Never.

Variations

  • Rejection sampling. Draw from an easy distribution, reject what you do not want; expected draws . rand10() from rand7() accepts 40 of 49 outcomes and uses calls on average (2.444 in our simulation).
  • Alias method (Walker, Vose): setup, per weighted sample.
  • Random walks. Papadimitriou's random-walk algorithm solves 2-SAT in expected steps; Schöning's walk gives the best simple exponential bound for 3-SAT. (The deterministic linear-time 2-SAT is in 2-SAT & Graph Colouring.)
  • Randomized incremental algorithms. Insert items in random order and the expected work collapses: Seidel's linear programming in fixed dimension and Welzl's smallest enclosing circle run in expected ; see Computational Geometry.
  • Color-coding (Alon, Yuster, Zwick, 1995): colour vertices randomly to find paths of length in time.
  • "Random element is good with constant probability" tricks. Majority element by sampling; "GCD of at least half the numbers" by picking random elements (Codeforces 364D); "make all numbers share a factor" by factoring random elements (Codeforces 1305F).
  • Sketching and streaming. Count-Min, AMS and HyperLogLog sketches; see Streaming Algorithms.
  • Monte Carlo simulation and Monte Carlo tree search. Estimate an answer by random sampling; error shrinks like .
  • Derandomization. Some randomized algorithms can be made deterministic with the method of conditional expectations or with -wise independent families of small size.

Practice ladder

Each problem is described in my own words; follow the link for the full statement. Full, tested solutions for the five that teach the core techniques.

1. Shuffle an Array (LeetCode 384) — Implement shuffle() (all orders equally likely) and reset().

Solution

Fisher–Yates on a copy. Checked: 60,000 shuffles of three elements, every order within 10% of 10,000.

import random


class Solution384:
    def __init__(self, nums):
        self.original = nums[:]
    def reset(self):
        return self.original[:]
    def shuffle(self):
        a = self.original[:]
        for i in range(len(a) - 1, 0, -1):
            j = random.randint(0, i)
            a[i], a[j] = a[j], a[i]
        return a

2. Linked List Random Node (LeetCode 382) — Return a uniformly random node's value from a linked list, ideally in extra space.

Solution

Reservoir sampling with : keep the -th node with probability .

import random


class ListNode:
    def __init__(self, val, next=None):
        self.val, self.next = val, next

class Solution382:
    def __init__(self, head):
        self.head = head
    def getRandom(self):
        chosen, i, node = None, 0, self.head
        while node:
            i += 1
            if random.randrange(i) == 0:      # keep the i-th node with probability 1/i
                chosen = node.val
            node = node.next
        return chosen

3. Random Pick Index (LeetCode 398) — Given an array with duplicates, return a random index of a target value.

Hint

Reservoir sampling over the indices equal to the target: the -th match replaces the answer with probability .

4. Implement Rand10() Using Rand7() (LeetCode 470) — Build a uniform 1..10 generator from a uniform 1..7 one.

Solution

Two calls give a uniform number in 1..49; accept 1..40 and map to 1..10; otherwise retry (Las Vegas). Expected calls: .

def rand10(rand7):
    while True:
        x = (rand7() - 1) * 7 + rand7()       # uniform on 1..49
        if x <= 40:                            # accept 40 of the 49 outcomes
            return (x - 1) % 10 + 1

5. Random Pick with Weight (LeetCode 528) — Return index with probability proportional to w[i].

Hint

Prefix sums; draw uniformly in ; binary search for the first prefix (Prefix Sums, Binary Search).

6. Insert Delete GetRandom O(1) (LeetCode 380) — A set with average insert, delete and uniform random element.

Hint

Array of values + hash map from value to index. Delete by swapping with the last element and popping.

7. Kth Largest Element in an Array (LeetCode 215) — Find the -th largest element.

Solution

Randomized quickselect, iterative, expected . Checked against sorting on 300 random arrays. (The tests include many equal values; for arrays made of one repeated value, use a three-way partition to stay linear.)

import random


def find_kth_largest(nums, k):
    target = len(nums) - k                     # index in sorted order
    lo, hi = 0, len(nums) - 1
    a = nums[:]
    while True:
        p = random.randint(lo, hi)
        a[p], a[hi] = a[hi], a[p]
        pivot, store = a[hi], lo
        for i in range(lo, hi):
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        if store == target:
            return a[store]
        if store < target:
            lo = store + 1
        else:
            hi = store - 1

8. Sort an Array (LeetCode 912) — Sort without built-ins in .

Hint

Quicksort with a fixed pivot times out on the sorted and all-equal tests. Use a random pivot and three-way partitioning, or merge sort.

9. Random Pick with Blacklist (LeetCode 710) — Uniform integer in not in a blacklist, with up to .

Hint

Draw from ; remap blacklisted values in that range to allowed values in the tail with a hash map. Rejection sampling also works when the blacklist is small relative to , but its expected cost blows up when it is not.

10. Random Flip Matrix (LeetCode 519) — Repeatedly return a random zero cell of a huge matrix and set it to one.

Hint

A lazy Fisher–Yates over the flattened indices: store only the swapped positions in a hash map.

11. Generate Random Point in a Circle (LeetCode 478) — Uniform point inside a circle.

Hint

Rejection from the bounding square (accept probability ), or polar coordinates with radius — not , which crowds points near the centre.

12. Online Majority Element In Subarray (LeetCode 1157) — Answer queries "which value occurs at least threshold times in arr[l..r]" where threshold is more than half the length.

Hint

A majority element is hit by a random pick from the range with probability . Try ~20 random picks; count occurrences of each candidate with binary search on its sorted position list. Failure probability per query.

13. Ghd (Codeforces 364D) — Find the largest dividing at least half of the numbers.

Hint

A random element is divisible by the answer with probability . Pick one, try its divisors, count multiples efficiently; repeat ~10 times.

14. Kuroni and the Punishment (Codeforces 1305F) — Fewest operations to make the gcd of an array exceed 1.

Hint

The answer is at most (make everything even), so at least half the elements change by at most 1 in an optimal solution. A random element is such an element with probability ; factor and test each prime factor. Repeat ~20 times. Seed from the clock — this problem is a hacking magnet.

Common mistakes & interview follow-ups

"Prove your shuffle is uniform." Count draw sequences (), show the map to permutations is a bijection. For the naive loop, the counting argument ( not divisible by for ) proves it cannot be uniform — without computing a single probability.

"Your stream has a billion items and you want 100 of them, with one pass." Reservoir sampling; mention Algorithm L if generating random numbers is the bottleneck, and the key for weights.

"Why is randomized quicksort even on sorted input?" The analysis depends only on ranks; every input has the same expected cost. Then mention the caveat: predictable seeds and adaptive adversaries.

"Is expected good enough?" Discuss tails: quickselect's chance of using more than work falls exponentially in ; when a hard bound is needed, use median of medians or introselect.

"How many times do you run Karger?" for failure probability . Show the telescoping product. Know that Karger–Stein reduces the total to .

"Verify a matrix product faster than multiplying." Freivalds; derive the 1/2 bound from one non-zero entry of ; one-sided error; rounds give .

"Las Vegas or Monte Carlo?" Be precise: quicksort is Las Vegas, Karger is Monte Carlo with one-sided error; you can turn Monte Carlo into Las Vegas only with a verifier.

Mistakes interviewers watch for: j in 0..n-1 in a shuffle; rand() % n; seeding inside a loop; fixed seeds in contest code; using Math.random() for tokens; forgetting to repeat a Monte Carlo algorithm; claiming randomized quicksort is never (it can be, just with tiny probability).

Quick quiz

1. A Monte Carlo algorithm is correct with probability 1/3 per run, and you can check an answer in . How do you turn it into a Las Vegas algorithm, and what is the expected number of runs?

Answer

Run, verify, repeat until the check passes. The number of runs is geometric with success probability 1/3: expected 3 runs.

2. In randomized quicksort, what is the probability that the smallest and largest elements are compared directly?

Answer

: they are compared only if one of them is the first pivot chosen from the whole array (the block between them is everything).

3. Why can the swap-with-any-position shuffle never be uniform for ?

Answer

It has equally likely runs spread over permutations. Uniformity would need each permutation to get runs, which is not an integer. The exact split is 4, 5, 5, 5, 4, 4.

4. In Algorithm R with , what is the probability that the 4th item of a 10-item stream ends up as the sample?

Answer

It enters with probability and then survives items 5..10 with probabilities : total .

5. One Karger run on a 10-vertex graph succeeds with probability at least what? About how many runs give failure probability below 1%?

Answer

. , so 208 runs.

6. Freivalds with errs with probability at most per round. How would you get error at most per round with a single round?

Answer

Work modulo a prime and draw each uniformly from . The same one-free-coordinate argument gives error at most per round (assuming the difference is non-zero modulo — true if entries are smaller than , or with high probability for a random prime).

Further reading / sources

  • Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms (1995) — the standard text: Las Vegas/Monte Carlo, quicksort tails, min-cut, Freivalds, hashing.
  • Michael Mitzenmacher and Eli Upfal, Probability and Computing (2nd ed., 2017) — gentler; balls and bins, power of two choices, Chernoff bounds.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS) — Chapter 5 (probabilistic analysis, indicator variables, random permutations), Chapter 7 (randomized quicksort), Chapter 9 (randomized select), Chapter 11 (universal hashing, 3rd ed. numbering).
  • Donald E. Knuth, The Art of Computer Programming, Vol. 2, §3.4.2 (random sampling and shuffling: Algorithms P and R).
  • David R. Karger, "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm", SODA 1993; David R. Karger and Clifford Stein, "A New Approach to the Minimum Cut Problem", JACM 43(4), 1996.
  • Rūsiņš Freivalds, "Probabilistic Machines Can Use Less Running Time", IFIP Congress 1977.
  • Michael O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory 12, 1980; Gary L. Miller, "Riemann's Hypothesis and Tests for Primality", JCSS 13, 1976.
  • Jeffrey S. Vitter, "Random Sampling with a Reservoir", ACM TOMS 11(1), 1985; Kim-Hung Li, "Reservoir-Sampling Algorithms of Time Complexity O(n(1 + log(N/n)))", ACM TOMS 20(4), 1994; Pavlos S. Efraimidis and Paul G. Spirakis, "Weighted random sampling with a reservoir", Information Processing Letters 97(5), 2006.
  • J. Lawrence Carter and Mark N. Wegman, "Universal Classes of Hash Functions", JCSS 18(2), 1979.
  • M. Douglas McIlroy, "A Killer Adversary for Quicksort", Software: Practice and Experience 29(4), 1999.
  • Richard Durstenfeld, "Algorithm 235: Random permutation", CACM 7(7), 1964.
  • Debian Security Advisory DSA-1571-1: openssl — predictable random number generator, 2008.
  • cp-algorithms: Primality tests (Miller–Rabin, deterministic base sets).

Lessons: module — Paradigms · previous — Bit Manipulation · next — Paradigms Capstone · course — DSA: Zero to Mastery.

Related Archon pages: Quick Sort · Quickselect & Order Statistics · Hash Tables · Treaps, Splay Trees & Skip Lists · Probabilistic Data Structures · Probability for Engineers · Greedy Algorithms · Union-Find · Network Flow.