Randomized Algorithms: Trading Certainty for Speed

"Sometimes the smartest move is to flip a coin. Randomness can dodge worst-case inputs an adversary would exploit, and let you sample an answer when computing the exact one is impossible. Giving up a little certainty buys a lot of speed."

Randomness as a Tool, Not a Bug

Randomness can break the correlation between a fixed input and an algorithm's choices: randomized quicksort still has an O(n²) worst case, but runs in expected O(n log n). CPython also salts many string hashes to make crafted collision attacks harder, though this is a runtime defense rather than a universal property of hashing. Sampling is useful not only when exact computation is impossible, but whenever an exact answer is possible yet too costly and a controlled estimate is sufficient.

Two Flavors of Randomized Algorithm

Las Vegas: always returns the correct answer, but the runtime is random. Randomized quicksort is the classic — the output is always sorted; only the speed depends on luck (and is excellent in expectation). You never get a wrong answer, just occasionally a slower run.
Monte Carlo: accepts error probability or approximation error in exchange for a bounded work budget. It need not take exactly the same fixed time on every input.

Knowing which guarantee you have — always-right-maybe-slow versus always-fast-maybe-wrong — tells you whether a randomized algorithm is safe for your use.

Randomness is a tool: it defeats adversarial worst cases (random pivots, salted hashes) and enables sampling when exact computation is infeasible. Las Vegas algorithms are always correct with random runtime; Monte Carlo algorithms use a bounded work budget while accepting controlled error or approximation risk.

The Gem: Reservoir Sampling

The most elegant randomized algorithm is reservoir sampling: pick a uniformly-random item from a stream of unknown, possibly enormous length, in O(1) space and one pass. The trick: keep the current pick; when the i-th item arrives, replace your pick with it with probability 1/i. When the stream ends, every item — first or billionth — had an equal chance of being chosen, provably. It's how you sample a random line from a file too big to hold in memory, or a random log entry from an endless feed. One variable, one pass, perfect uniformity, no idea how long the stream is. Pure randomized magic.

Pippa's Confession

Reservoir sampling broke my intuition — how can each of a billion streaming items be equally likely if I only keep one variable and never see the total count? Dad walked me through the 1/i replacement probability and the algebra worked out to exactly uniform. I sat with it until it clicked: randomness, used precisely, can guarantee fairness without global knowledge. That's the deep lesson — a pinch of well-chosen randomness can buy properties (unpredictability, uniformity, expected speed) that no deterministic trick gives you as cheaply.

Code

Reservoir sampling and Monte Carlo pi·python

import random

# RESERVOIR SAMPLING: one uniformly-random item from a stream of unknown length.
# O(1) space, one pass — and provably uniform over the whole stream.
def reservoir_sample(stream):
    pick = None
    for i, item in enumerate(stream, start=1):
        # replace the current pick with probability 1/i
        if random.randint(1, i) == 1:
            pick = item
    return pick
# When the stream ends, every item had an equal 1/n chance — without ever
# knowing n in advance. One variable, one pass.

# MONTE CARLO: estimate pi by random sampling (fixed work, approximate answer).
def estimate_pi(samples):
    inside = 0
    for _ in range(samples):
        x, y = random.random(), random.random()
        if x*x + y*y <= 1.0:        # inside the quarter circle?
            inside += 1
    return 4 * inside / samples     # ratio of areas -> approximates pi
# More samples -> closer estimate. Trading exactness for a fast approximation.

# (Randomized quicksort from the sorting track is the Las Vegas classic:
#  a random pivot makes the O(n^2) worst case practically impossible.)

Exercise

Explain why a RANDOM pivot makes quicksort's O(n²) worst case practically impossible, even though that worst case still technically exists. Is randomized quicksort Las Vegas or Monte Carlo, and why? Separately: in reservoir sampling, why does replacing the pick with probability 1/i give every item an equal final chance?

Hint

A random pivot means no specific input can reliably trigger bad splits — an adversary can't predict your choices, so worst case needs astronomically unlucky randomness. It's Las Vegas: always correctly sorted, only the runtime is random. Reservoir: the i-th item is kept with prob 1/i, and survives all later replacements with prob (i/(i+1))·…·((n-1)/n), which telescopes to 1/n for every item.

Randomness as a Tool, Not a Bug

Two Flavors of Randomized Algorithm

The Gem: Reservoir Sampling

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0