Chapter 6 · Design & Analysis of Algorithms

Randomized
Algorithms

Let the algorithm flip coins. On a worst-case world, internal randomization can defeat adversarial inputs and unlock solutions that deterministic algorithms cannot match efficiently.

🎲 Monte Carlo — fast, small error ✅ Las Vegas — always correct, fast in expectation ✔ Freivalds O(n²) 🔩 Nuts & Bolts O(n log n) expected

🎲

01 The Randomization Idea

"When one thinks about random processes in the context of computation, it is usually in one of two distinct ways. One view is to consider the world as behaving randomly — this is average-case analysis. A second view is to consider algorithms that behave randomly: the world provides the same worst-case input as always, but we allow the algorithm to make random decisions as it processes the input."

Monte Carlo Algorithms

Fast, small error probability

Always run in polynomial time. Return the correct answer with high probability. The error probability can be reduced arbitrarily by repetition.

Example: Freivalds' algorithm

Las Vegas Algorithms

Always correct, fast in expectation

Always return the correct answer. Running time is a random variable that is small in expectation (over the algorithm's own coin flips).

Example: Nuts & Bolts, Randomized QuickSort

Why randomize?

Efficient deterministic algorithms that always give the correct answer are a special case of efficient randomized algorithms that only need to give the correct answer with high probability (Monte Carlo). They are also a special case of Las Vegas algorithms. Even in a worst-case world, an algorithm that performs its own "internal" randomization may be able to offset certain worst-case phenomena.

02 Freivalds' Verification of Matrix Multiplication

Given three n×n matrices A, B, and C, decide whether AB = C. The naïve approach computes AB from scratch (same cost as matrix multiplication, O(n³) or O(n²·⁸) via Strassen). Freivalds' idea achieves O(n²) with only a 1/2 chance of error.

Algorithm — O(n²) per round, error ≤ 1/2

Freivalds(A, B, C)

Choose α ∈ {0,1}ⁿ uniformly at random // random bit vector β = A(Bα) // two matrix-vector products: O(n²) γ = Cα if β = γ: return "AB = C" else: return "AB ≠ C"

Correctness

If AB = C, then β = A(Bα) = (AB)α = Cα = γ for any α. The algorithm always returns the correct answer in this case.

The interesting case is when AB ≠ C:

Key Theorem

Error probability ≤ 1/2

If AB ≠ C, then Pr[A(Bα) = Cα] ≤ 1/2 over a uniformly random α ∈ {0,1}ⁿ.

Proof — the flipping argument

Suppose AB ≠ C but for some α, (AB−C)α = 0. Since AB−C ≠ 0, it has some non-zero entry d at row i, column j.

Consider α' obtained by flipping the j-th bit of α. Then the i-th coordinate of (AB−C)α' differs from that of (AB−C)α by exactly d ≠ 0. So (AB−C)α' ≠ 0 → A(Bα') ≠ Cα'.

This gives a bijection: for each "bad" α (where algorithm errs), there is a distinct "good" α' (where it doesn't). So at least half the bit vectors are "good" → error probability ≤ 1/2. ■

Reducing Error by Repetition

Run Freivalds k times with independent random vectors α₁,…,αₖ. Return "AB = C" only if all k rounds agree. The probability of error is at most (1/2)ᵏ:

\[\Pr[\text{error after } k \text{ rounds}] \le \left(\frac{1}{2}\right)^k\]

✔ Freivalds' Simulator Monte Carlo

Choose random α, compute β=A(Bα) and γ=Cα, compare. If equal → "AB=C". Click to run.

Rounds run: 0 | Errors detected: 0 | Current error prob: —

Error probability upper bound

Dramatic speed-up

Strassen computes AB in O(n²·⁸⁰⁷). Freivalds verifies AB=C in O(n²) per round with error ≤ 1/2. For k=30 rounds, error ≤ 10⁻⁹ and total time is 30·O(n²) — still vastly faster than recomputing AB for large n.

03 Nuts and Bolts

We are given n bolts and n nuts of different sizes with a one-to-one correspondence. We cannot compare two bolts directly or two nuts directly — only a bolt against a nut. Find all matching pairs.

Constraint

Deterministic algorithms achieving O(n log n) worst-case exist but are "highly technical and quite involved." The randomized Las Vegas approach gives O(n log n) expected time with a simple, elegant algorithm based on the divide-and-conquer paradigm.

The Algorithm — Randomized Pivot

Las Vegas Algorithm — O(n log n) expected

NutsAndBolts(bolts, nuts)

if |bolts| ≤ 1: return b ← random bolt from bolts // random pivot! m ← nut matching b // partition nuts around m: O(n) nuts_small, nuts_large ← partition(nuts, m) bolts_small, bolts_large ← partition(bolts, b) // partition bolts around b: O(n) // Total comparisons this step: 2n−1 NutsAndBolts(bolts_small, nuts_small) // recurse left NutsAndBolts(bolts_large, nuts_large) // recurse right

Why nuts first, then bolts?

We pick a random bolt b, find its matching nut m, then use m to partition all nuts (smaller/larger than m), and then use b to partition the remaining bolts. This two-pass partition is necessary because we can't compare bolts to bolts or nuts to nuts.

🔩 Nuts & Bolts Simulator Las Vegas

8 bolts and 8 nuts to match. Press Next Step to run one level of the randomized algorithm.

Comparisons: 0

Matches found: 0 / 8

Bolts (B)

Nuts (N)

Expected Time Analysis

Let T(n) = expected comparisons. Let T(n,j) = expected comparisons when the chosen bolt has rank j (is the j-th smallest). Two passes of partition: 2n−1 comparisons.

\[T(n,j) = 2n-1 + T(j-1) + T(n-j)\]

\[T(n) = \frac{1}{n}\sum_{j=1}^{n} T(n,j) = 2n-1 + \frac{2}{n}\sum_{j=0}^{n-1}T(j)\]

The analysis proceeds by multiplying both sides by n, writing the same for n−1, and subtracting:

Key recurrence after subtraction

nT(n) − (n−1)T(n−1) = 4n−3 + 2T(n−1)

Rearranged

T(n)/(n+1) = T(n−1)/n + (4n−3)/(n(n+1)) < T(n−1)/n + 4/n

Telescoping

T(n)/(n+1) < 4/n + 4/(n−1) + … + 4/1 = 4·H(n) < 4(1 + ln n)

Conclusion

T(n) = O(n log n)

\[T(n) = O(n \log n)\]

Chapter Summary

Algorithm	Type	Time	Guarantee	Key Trick
Freivalds	Monte Carlo	O(n²) per round	Error ≤ (1/2)ᵏ after k rounds	Bit-flip bijection
Nuts & Bolts	Las Vegas	O(n log n) expected	Always correct	Random pivot + two-pass partition

The fundamental trade-off

Monte Carlo trades correctness probability for speed. Las Vegas trades deterministic running time for expected running time. Both are strictly more powerful than deterministic algorithms in many settings — the randomness offsets adversarial worst-case inputs that would break any deterministic strategy.

Connection to sorting

Nuts & Bolts is essentially Randomized QuickSort with the twist that you can't directly compare two elements of the same type. The same analysis gives T(n) = O(n log n) expected — the harmonic series argument is identical to QuickSort's analysis.