Why would an algorithm flip coins?
An algorithm is supposed to be a precise recipe. Why would anyone put a coin toss into one? Three reasons keep coming up.
Randomness defeats adversaries. Quicksort that always picks the first element as its pivot is quadratic on already-sorted input, and sorted input is common. Pick the pivot at random and no input is bad any more: the slow cases still exist, but they depend on the coin flips, which nobody outside can predict or arrange. The same idea protects hash tables from attackers who would otherwise send keys that all collide.
Randomness makes hard things simple. Choosing a random sample, spreading requests over servers, or testing whether a 600-digit number is prime all have simple randomised solutions where the deterministic ones are complicated or slow.
Randomness lets a small memory summarise a huge stream. A website wants to know how many different visitors it had today, out of a billion page views. Remembering every visitor takes gigabytes. A HyperLogLog sketch answers within a couple of per cent using a few kilobytes, by looking at random-looking bits of hashed IDs.
Throughout this lesson, "random" means the algorithm's own coin flips. We make no assumption that the input is random; the guarantees hold for every input, on average over the coins. That distinction, between average over the algorithm's choices and average over inputs, is the heart of the subject.
Las Vegas and Monte Carlo
Definition— randomised algorithm
A randomised algorithm may call a source of random bits. Its running time, and possibly its output, are then random variables, and we analyse them for a fixed, worst-case input, with probability taken over the random bits only.
Definition— Las Vegas, Monte Carlo
A Las Vegas algorithm always returns a correct answer; only its running time is random, and we bound its expected running time. A Monte Carlo algorithm has a bounded running time but may return a wrong answer with some bounded probability. It has one-sided error if it can err only in one direction (for example, it may say "composite" only when the number really is composite, but may wrongly say "prime").
Randomised quicksort is Las Vegas: always sorted, sometimes slower. Rabin–Karp with its verification step, from String algorithms, is Las Vegas too; drop the verification and it becomes Monte Carlo. The Miller–Rabin primality test is Monte Carlo with one-sided error: a "composite" verdict is always right, and a composite number passes one round with probability at most . Cryptographic libraries use it to generate the large primes behind RSA keys. Freivalds' algorithm checks whether for matrices by multiplying both sides by a random 0/1 vector, costing instead of a full multiplication; a wrong survives a trial with probability at most .
Theorem— Amplification
If a Monte Carlo algorithm with one-sided error is wrong with probability at most on each run, and runs use independent random bits, then running it times and answering "composite" (say) if any run does, errs with probability at most .
Proof
The combined answer is wrong only if every one of the runs is wrong. The runs are independent, so the probability of that is the product of the individual probabilities, at most .
∎
Forty rounds of Miller–Rabin leave an error probability below , far smaller than the chance of a hardware fault during the computation. Two more conversions are worth knowing. A Las Vegas algorithm becomes Monte Carlo by stopping it at, say, three times its expected running time and answering "don't know"; by Markov's inequality that happens with probability at most . A Monte Carlo algorithm becomes Las Vegas if you can check its answer cheaply and repeat until the check passes.
Randomised quicksort, analysed
You met quicksort in Searching and sorting: pick a pivot, partition the rest into smaller and larger elements, recurse. With a uniformly random pivot, how many comparisons does it make?
Theorem— Expected comparisons of randomised quicksort
On any input of distinct keys, randomised quicksort makes at most comparisons in expectation, where . (The exact expectation is .)
Proof
Name the keys in sorted order . Two keys are compared only when one of them is the current pivot, and a pivot is never compared again after its partition, so each pair is compared at most once. Let be 1 if and are compared () and 0 otherwise; the total number of comparisons is .
Consider the block , which has keys. As long as no pivot has been chosen from inside , all of its keys stay together in one subarray. The first pivot chosen from decides the pair's fate: if it is or , the two are compared; if it is any key strictly between them, they are separated into different subarrays and never meet. Because pivots are uniform over the current subarray, every key of is equally likely to be that first pivot. So , and by linearity of expectation,
Since , this is at most .
∎
Linearity of expectation did the heavy lifting: the are far from independent, but expectations add regardless. Lumenary Math's Conditional probability and independence lesson covers the probability used here.
import math, random
def quicksort(a, choose_pivot):
"""In-place quicksort with an explicit stack; returns the sorted list and the comparison count."""
a, comparisons = list(a), 0
stack = [(0, len(a) - 1)]
while stack:
lo, hi = stack.pop()
if lo >= hi:
continue
p = choose_pivot(lo, hi)
a[p], a[hi] = a[hi], a[p] # move the pivot to the end, then partition
pivot, i = a[hi], lo
for j in range(lo, hi):
comparisons += 1
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
stack += [(lo, i - 1), (i + 1, hi)]
return a, comparisons
n = 2000
already_sorted = list(range(n))
_, c = quicksort(already_sorted, lambda lo, hi: lo) # deterministic: first element as pivot
print(f"first-element pivot on sorted input: {c:,} comparisons (n(n-1)/2 = {n * (n - 1) // 2:,})")
rng = random.Random(1)
counts = []
for trial in range(20):
result, c = quicksort(already_sorted, lambda lo, hi: rng.randint(lo, hi))
assert result == already_sorted
counts.append(c)
harmonic = sum(1 / k for k in range(1, n + 1))
print(f"random pivot, 20 runs: min {min(counts):,}, mean {sum(counts) / len(counts):,.0f}, max {max(counts):,}")
print(f"exact expectation 2(n+1)H_n - 4n = {2 * (n + 1) * harmonic - 4 * n:,.0f}; 2n ln n = {2 * n * math.log(n):,.0f}")On sorted input the deterministic version makes about two million comparisons, eighty times more than the randomised one. Notice also how tightly the twenty random runs cluster around the expectation. That is not luck: the number of comparisons is concentrated, and the probability of exceeding the expectation by a constant factor falls off faster than any power of . "Expected " is, in practice, a promise.
Sampling a stream: reservoir sampling
A server writes a billion log lines a day, and you want 1,000 chosen uniformly at random, in one pass, without knowing in advance how many lines there will be and without storing them. Reservoir sampling (Algorithm R, analysed by Vitter in 1985) does it with memory for just the sample:
- Keep the first items.
- When item number arrives (), pick a random integer from to . If , the new item replaces the -th item of the reservoir; otherwise discard it.
Theorem— Reservoir sampling is uniform
After items, each of them is in the reservoir with probability exactly .
Proof
By induction on . For every item is kept: probability . Suppose the claim holds after items, and item arrives. It enters with probability , as required. An earlier item was in the reservoir with probability ; it is evicted only if the new item enters and lands on its slot, which happens with probability . So it is still there with probability .
∎
A slightly longer induction shows more: every set of items is equally likely to be the reservoir, so it is a genuinely uniform sample, not just one with the right marginal probabilities.
import random
from collections import Counter
def reservoir_sample(stream, k, rng):
"""A uniform random sample of k items from a stream of unknown length, in one pass and O(k) memory."""
sample = []
for i, item in enumerate(stream): # item i is the (i+1)-th item seen
if i < k:
sample.append(item)
else:
j = rng.randrange(i + 1) # uniform in 0..i
if j < k: # happens with probability k/(i+1)
sample[j] = item
return sample
def log_lines():
"""A stand-in for a stream too long to store: we never know its length in advance."""
cities = ["Accra", "Bogotá", "Chennai", "Dhaka", "Hanoi", "Manila", "Nairobi", "Seoul"]
for i in range(1, 100_001):
yield f"request {i:6} from {cities[(i * 7) % len(cities)]}"
rng = random.Random(2024)
for line in reservoir_sample(log_lines(), 4, rng):
print(line)
# Is it really uniform? Sample 3 of 10 items many times and count how often each is chosen.
tally = Counter()
trials = 30_000
for _ in range(trials):
tally.update(reservoir_sample(range(10), 3, rng))
print({item: round(tally[item] / trials, 3) for item in range(10)}, "(each should be near 0.3)")The same pattern, keep a few items and replace them with carefully chosen probabilities, extends to weighted sampling (one of the exercises), to sampling over a sliding time window, and to distributed sampling where each machine keeps a reservoir and the reservoirs are merged.
Hashing to spread the load
Hash functions turn up whenever work must be divided: which of 50 cache servers holds a user's session, which shard of a database stores a row, which bucket of a hash table holds a key. A good hash behaves like a random function, so each key lands on a uniformly random server, independently of the others. Placing keys on servers is then the balls-into-bins experiment. The average load is ; when , the busiest server gets about keys, a slowly growing but real imbalance. A surprising improvement, the power of two choices: hash each key to two random servers and put it on the less loaded one. The maximum load drops to about , exponentially better, and load balancers use this idea to pick between two random back ends.
Adversaries again. As Hash tables showed with hash flooding, a fixed, public hash function lets an attacker choose keys that all collide. The defence is randomness again: choose the hash function at random when the program starts, from a family where any two distinct keys collide with probability about (Carter and Wegman's universal hashing, 1979). That is why Python's hash() of a string changes from one run to the next (PEP 456). A practical consequence: never use hash() for anything stored on disk or shared between processes. Use hashlib, as every runnable block in this lesson does.
Changing the number of servers. The naive assignment server = h(key) % m has a nasty property: when changes from 10 to 11, a key stays put only if , which holds for only about one key in 11. Ninety per cent of the keys move, and a cache cluster that adds one machine loses almost all its contents at once. Two schemes fix this:
- Consistent hashing (Karger and colleagues, 1997) places both servers and keys at hashed positions on a circle; each key belongs to the next server clockwise. Adding a server takes over only the keys between it and its predecessor, about of them. It underlies many distributed caches and databases you will meet in Distributed systems.
- Rendezvous hashing (highest random weight; Thaler and Ravishankar, 1998) is even simpler: for each key, compute a hash of the pair (server, key) for every server and pick the server with the highest score. Removing a server moves only its own keys; adding one moves only the keys it now wins. You will implement it in the exercises.
Bloom filters: membership with a small lie
A database keeps data in hundreds of files on disk. Before reading a file to look for a key, it would like to know whether the key could possibly be there. A Bloom filter answers "definitely not" or "probably yes" using about ten bits per key, whatever the size of the keys.
Definition— Bloom filter
A Bloom filter is an array of bits, all initially 0, with hash functions mapping items to positions . To add an item, set the bits to 1. To query an item, answer "probably present" if all of its bits are 1, and "absent" otherwise.
An item that was added always has all its bits set, so there are no false negatives. A false positive happens when an item that was never added finds all its bits set by other items. After insertions, a particular bit is still 0 with probability , so (treating bits as independent, which is accurate for realistic sizes) the false-positive rate is
More hash functions set more bits per item but also check more bits per query; the rate is minimised at , where half the bits are set, giving . Turned around: a 1% false-positive rate needs about bits per item, and every further 4.8 bits per item cuts the rate by ten.
import hashlib, math
class BloomFilter:
def __init__(self, m_bits, k):
self.m, self.k = m_bits, k
self.bits = bytearray((m_bits + 7) // 8)
def _positions(self, item):
# Two 64-bit hashes from one digest; the k positions are h1 + i*h2 (Kirsch and Mitzenmacher).
d = hashlib.blake2b(item.encode(), digest_size=16).digest()
h1, h2 = int.from_bytes(d[:8], "little"), int.from_bytes(d[8:], "little") | 1
return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, item):
for p in self._positions(item):
self.bits[p // 8] |= 1 << (p % 8)
def __contains__(self, item):
return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(item))
n = 10_000 # items we will insert
for bits_per_item in (4, 8, 10, 16):
m = bits_per_item * n
k = max(1, round(bits_per_item * math.log(2))) # the optimal number of hash functions
bf = BloomFilter(m, k)
for i in range(n):
bf.add(f"user-{i}")
assert all(f"user-{i}" in bf for i in range(n)) # never a false negative
probes = 50_000
false_pos = sum(f"stranger-{i}" in bf for i in range(probes))
predicted = (1 - math.exp(-k * n / m)) ** k
print(f"{bits_per_item:2} bits/item, k={k:2}: false positives {false_pos / probes:.4f}, "
f"formula {predicted:.4f}, memory {len(bf.bits):,} bytes for {n:,} items")Ten thousand keys in 12.5 kilobytes with under 1% false positives, regardless of whether the keys are short IDs or long URLs. Computing independent hashes is the expensive part, so the code uses a trick of Kirsch and Mitzenmacher: two hashes generate all positions as , with no measurable loss.
Where they live: databases built on log-structured merge trees, such as RocksDB and Cassandra, keep a Bloom filter for every on-disk file and skip any file the filter rules out, which saves most of the disk reads for keys that are absent (more in Databases). Standard Bloom filters cannot delete items, since clearing a bit might erase evidence of another item; counting Bloom filters and cuckoo filters support deletion at some extra cost.
Sketches: counting without remembering
A sketch is a small summary of a stream that answers one kind of question approximately, with error bounds that hold with high probability. Two are worth knowing by heart.
Count-min: how often did this item appear?
A count-min sketch keeps rows of counters, with an independent hash function per row. To add an item, increment one counter in each row, the one its row's hash selects. To estimate an item's count, take the minimum of its counters. Each counter holds the item's true count plus the counts of whatever else collided there, so every row overestimates, and the minimum is the least-polluted row.
Theorem— Count-min error bound
Let be the total of all counts. With columns and rows, every estimate is at least the true count, and exceeds it by more than with probability at most .
Proof
Fix an item and one row. The excess in its counter is the total count of other items hashed to the same column. Each other item lands there with probability (for a pairwise-independent hash), so the expected excess is at most . By Markov's inequality, the excess exceeds with probability at most . The rows use independent hash functions, so all rows exceed it, which is what it takes for the minimum to exceed it, with probability at most .
∎
The guarantee is relative to the total , so count-min is accurate for frequent items ("heavy hitters": the most-requested URLs, the busiest IP addresses) and nearly useless for rare ones, which is usually what you want.
HyperLogLog: how many different items?
Counting distinct items is harder, because you cannot tell whether you have seen an item before without remembering it. The insight of Flajolet and Martin (1985), refined into HyperLogLog (2007): hash each item to a string of random-looking bits. A hash that begins with zeros and then a 1 occurs with probability , so if the largest such seen so far is 20, you have probably seen around a million distinct items. Repeats do not matter, since an item hashes the same way every time. One such maximum is very noisy, so HyperLogLog uses the first bits of the hash to pick one of registers, keeps a separate maximum in each, and combines them with a bias-corrected harmonic mean. The standard error is about , and each register needs only 6 bits.
import hashlib, math, random
from collections import Counter
def h64(item, seed=0):
"""A 64-bit hash of a string; different seeds give independent-looking hash functions."""
d = hashlib.blake2b(item.encode(), digest_size=8, salt=seed.to_bytes(16, "little")).digest()
return int.from_bytes(d, "big")
class CountMin:
def __init__(self, width, depth):
self.w, self.d = width, depth
self.rows = [[0] * width for _ in range(depth)]
def add(self, item, count=1):
for r in range(self.d):
self.rows[r][h64(item, r) % self.w] += count
def estimate(self, item):
return min(self.rows[r][h64(item, r) % self.w] for r in range(self.d)) # never too low
class HyperLogLog:
def __init__(self, b=10):
self.b, self.m = b, 1 << b
self.reg = [0] * self.m
def add(self, item):
x = h64(item, 99)
j = x >> (64 - self.b) # the first b bits pick a register
rest = x & ((1 << (64 - self.b)) - 1)
rank = (64 - self.b) - rest.bit_length() + 1 # position of the first 1-bit in the rest
self.reg[j] = max(self.reg[j], rank)
def estimate(self):
m = self.m
raw = 0.7213 / (1 + 1.079 / m) * m * m / sum(2.0 ** -r for r in self.reg)
zeros = self.reg.count(0)
if raw <= 2.5 * m and zeros: # small counts: linear counting is better
return m * math.log(m / zeros)
return raw
# A stream of page views where popularity follows a power law, as on real websites.
rng = random.Random(5)
pages = [f"/page/{r}" for r in range(1, 20_001)]
weights = [1 / r for r in range(1, 20_001)]
stream = rng.choices(pages, weights, k=60_000)
truth = Counter(stream)
cms, hll = CountMin(width=1000, depth=4), HyperLogLog(b=10)
for page in stream:
cms.add(page)
hll.add(page)
print("count-min sketch (4 x 1000 counters):")
for page, true_count in truth.most_common(3) + [("/page/5000", truth["/page/5000"])]:
print(f" {page:11} true {true_count:5}, estimate {cms.estimate(page):5}")
print(f" error bound e/w * N = {math.e / 1000 * len(stream):.0f} (holds with probability >= 1 - e^-4)")
print(f"HyperLogLog (1024 registers of a few bits): distinct pages true {len(truth):,}, "
f"estimate {hll.estimate():,.0f} (typical error 1.04/sqrt(1024) = {1.04 / 32:.1%})")The popular pages are estimated within about 1%; the rare page is overestimated by a couple of dozen, well inside the bound. The HyperLogLog, using 1,024 small registers, lands within a few per cent of the true number of distinct pages. Both sketches are mergeable: two count-min sketches with the same hash functions add counter by counter, and two HyperLogLogs merge by taking the maximum of each register. So a thousand servers can each sketch their own traffic and a central service can combine them, which is how these structures are used at scale. Redis offers HyperLogLog with 12 KB per counter and a standard error of 0.81%, and analytics databases offer APPROX_COUNT_DISTINCT-style functions built on HyperLogLog variants.
Seeded randomness and real randomness
Computers usually do not flip real coins. Python's random module is a pseudorandom number generator (the Mersenne Twister): a deterministic function that turns a starting seed into a long sequence that passes statistical tests for randomness. That determinism is a feature for engineering:
- Reproducibility. Every runnable block in this lesson creates its own
random.Random(seed), so it prints the same thing every time, here and in Lumenary's test suite. Record the seed of every simulation and experiment; a result you cannot reproduce is a result you cannot debug. (NumPy's equivalent isnumpy.random.default_rng(seed).) - Isolation. A private
random.Randominstance, rather than the module-level functions, keeps one component's randomness from shifting another's. - Testing randomised code. Fix the seed in unit tests, and for statistical properties test with tolerances over many trials, as the reservoir demo did.
Pseudorandomness is the wrong tool for secrets. The Mersenne Twister's entire future output can be computed from 624 consecutive 32-bit outputs, so session tokens, password-reset links and keys generated with random can be predicted. Use the secrets module (or os.urandom), which draws on the operating system's cryptographically secure generator; Applied cryptography explains what "cryptographically secure" means.
Common misconceptions
Misconception
"A randomised algorithm assumes random input." It assumes nothing about the input. Average-case analysis of a deterministic algorithm averages over inputs and can be defeated by a bad input; a randomised algorithm's guarantees hold for every input, averaged over its own coins.
Misconception
"Randomised means unreliable." Las Vegas algorithms are always correct. Monte Carlo error can be driven below the rate of hardware faults by a few repetitions. And for quicksort, the running time is so concentrated that a slow run is less likely than a cosmic-ray bit flip.
Misconception
"A Bloom filter can say an item is absent when it is present." Never: an added item's bits stay set. Errors go only the other way. (A filter that supports deletion by clearing bits would break this, which is why deletion needs a different design.)
Misconception
"hash(s) is a stable fingerprint of a string." It changes from one run of Python to the next, by design. Use hashlib for anything that must be stable.
Exercises
1. Randomness in algorithms
Warm-upHumanWhich of these are Las Vegas algorithms (always correct, random running time)? Select all that apply.
2. Randomness in algorithms
Warm-upHumanA Monte Carlo test with one-sided error wrongly accepts a bad input with probability at most per run, independently across runs. What is the smallest number of runs that guarantees an error probability below ?
3. Randomness in algorithms
CoreHumanRandomised quicksort sorts 100 distinct keys. What is the probability that the 3rd-smallest and the 7th-smallest keys are ever compared with each other?
4. Randomness in algorithms
CoreHumanYou will store keys in a Bloom filter of bits. How many hash functions minimise the false-positive rate? Give the nearest whole number.
5. Randomness in algorithms
CoreComputationalThe starter assigns keys to servers with score(key) % len(servers). It spreads keys evenly, but when a server is added or removed almost every key moves. Rewrite owner(key, servers) using rendezvous hashing: return the server with the highest score(server + "|" + key). Keep the score helper as it is (it is stable across runs, unlike hash).
6. Randomness in algorithms
CoreComputationalComplete the CountMin class. add(item, count=1) increments, in each row r, the counter at column h(item, r) % self.w; estimate(item) returns the minimum of the item's counters across the rows. The hash helper h is provided.
7. Randomness in algorithms
StretchComputationalWeighted reservoir sampling (Efraimidis and Spirakis, 2006). Each stream item comes with a positive weight . Give it the key , where is uniform in , and keep the items with the largest keys, using a min-heap of size (Python's heapq, from the Heaps lesson; the heap holds (key, item) pairs). Write weighted_sample(stream, k, rng) where stream yields (item, weight) pairs and rng is a random.Random; return a list of the chosen items. With , each item must be chosen with probability proportional to its weight.
8. Randomness in algorithms
Warm-upHumanFor which of these should you use the secrets module (or os.urandom) rather than a seeded random.Random? Select all that apply.
Further reading and resources
- Random sampling with a reservoir · Jeffrey S. Vitter · 1985
- Space/time trade-offs in hash coding with allowable errors · Burton H. Bloom · 1970The original Bloom filter paper.
- An improved data stream summary: the count-min sketch and its applications · Graham Cormode and S. Muthukrishnan · 2005
- HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm · Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier · 2007
- HyperLogLog in practice · Stefan Heule, Marc Nunkesser and Alexander Hall · 2013Google's engineering improvements (HyperLogLog++).
- Balanced allocations · Yossi Azar, Andrei Z. Broder, Anna R. Karlin and Eli Upfal · 1999The power of two choices.
- Consistent hashing and random trees · David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy et al. · 1997
- Universal classes of hash functions · J. Lawrence Carter and Mark N. Wegman · 1979
- PEP 456: Secure and interchangeable hash algorithmWhy Python's string hashes are randomised per process.
- Redis HyperLogLog documentation