Randomized Algorithms — Algorithms Course

What you'll learn

Sometimes the simplest fast algorithm flips a coin. Randomized algorithms use random choices to sidestep worst cases, sample fairly from streams, and solve problems that are awkward deterministically — often with dead-simple code and strong expected guarantees.

By the end you'll be able to:

Explain why randomness helps
Tell Monte Carlo from Las Vegas algorithms
Use reservoir sampling and randomized pivots

Why randomize?

A deterministic algorithm always processes a given input the same way, so an adversary can craft the input that triggers its worst case (a sorted array for last-element-pivot quicksort). Randomizing the algorithm's choices removes that predictability: no single input is reliably bad, because the behavior depends on coin flips the adversary can't see. We then reason about expected performance.

Monte Carlo vs Las Vegas

Randomized algorithms come in two flavors, trading which quantity is uncertain:

	Las Vegas	Monte Carlo
`Answer`	Always correct	Correct with high probability
`Running time`	Random (expected bound)	Fixed / bounded
`Example`	Randomized quicksort	Miller-Rabin primality
`Repeat to...`	(already correct)	Boost confidence

Note

Mnemonic: Las Vegas always gives the right answer but you gamble on time; Monte Carlo takes fixed time but you gamble on correctness — and can rerun to shrink the error probability as low as you like.

Randomized quicksort

Choosing the pivot uniformly at random makes quicksort a Las Vegas algorithm: the answer is always sorted, and the expected time is O(n log n) on every input — the adversary can no longer force O(n²). The same idea gives randomized quickselect its expected O(n) (Module 10).

Reservoir sampling

How do you pick k items uniformly at random from a stream of unknown length — using only O(k) memory and one pass? Reservoir sampling: keep the first k, then for the i-th item replace a random reservoir slot with probability k/i. Every item ends up equally likely:

Language

reservoir_sample.py

import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)          # fill the reservoir
        else:
            j = random.randint(0, i)        # 0..i inclusive
            if j < k:
                reservoir[j] = item         # keep with probability k/(i+1)
    return reservoir

Key idea

A one-line proof by induction shows each of the n items survives with probability exactly k/n. It's how you sample logs, tweets, or any stream too large to store — randomness turning an impossible-looking constraint into a five-line loop. Karger's randomized min-cut is another gem: repeatedly contract a random edge, and with enough tries you find the minimum cut.

Recap & quick check

Key takeaways

Randomization defeats worst-case adversaries by making behavior unpredictable.
Las Vegas: always correct, random running time (e.g. randomized quicksort).
Monte Carlo: fixed time, correct with high probability (e.g. Miller-Rabin) — rerun to boost confidence.
Random pivots give quicksort expected O(n log n) on every input.
Reservoir sampling picks k items uniformly from a stream in one pass, O(k) memory.

Quick check

1. A Las Vegas algorithm has which property?

2. A Monte Carlo algorithm has which property?

3. Why randomize quicksort's pivot?

4. Reservoir sampling keeps each stream item with probability:

From randomness to geometry: algorithms on points and lines. Next up: Module 34 — Computational Geometry.