Sampling a Stream You Can't Store
In short: to pick k items uniformly at random from a stream whose total
length you don't know in advance, keep the first k items, then for every
later item i (0-indexed), draw a random j between 0 and i. If j < k,
that item swaps into slot j of the reservoir; otherwise it's dropped. Item
i ends up with exactly a k / (i + 1) chance of surviving, and working
through the algebra shows every item in the whole stream — no matter when
it arrived — ends up with the same k / n chance of being in the final
reservoir. The reservoir never grows past k items, however long the stream
runs.
Audit a fair sample of a day's requests
Quarry can't store a full day of request logs just to pick a few for a spot-check, but it can prove the sample it does keep is fair by re-running the draw many times and counting how often each request survives:
With 5 requests and a reservoir of 2, every request should appear in roughly
1000 * 2 / 5 = 400 of the 1000 trials. Every seeded trial is
reproducible — the same seed and trial index always draw the same j
values, which is what makes sample_counts itself deterministic even though
each individual draw is random.
Watch one stream of 5 items fill a 2-cell reservoir, replace once, get rejected once, then replace again:
Each later item rolls a random j in [0, i]. j < k swaps it in; j >= k rejects it. The reservoir never grows past k cells.
Item 0, "p", fills the first empty slot — nothing to roll yet. 2 cells. At index 0.
Why item 0 doesn't get an unfair head start
The naive worry is that early items had "more chances" to be knocked out, so
they should be rarer in the reservoir than late ones. The algebra says
otherwise: item i's chance of surviving every later round multiplies
out to exactly k / n, the same for every i:
from fractions import Fraction
def survival_chance(i, n, k):
# P(kept at step i) * P(not bumped at each later DRAW, which only
# happens once the reservoir is full — steps before k are free fills)
p = Fraction(1) if i < k else Fraction(k, i + 1)
for later in range(max(i + 1, k), n):
p *= Fraction(later, later + 1) # P(not bumped) = 1 - 1/(later+1) = later/(later+1)
return p
print(survival_chance(0, 5, 2), survival_chance(4, 5, 2))Sampling while filtering out noise
Bot traffic shouldn't count toward the sample at all — not even toward the
position i that decides replacement odds. Skipping banned items without
adjusting i would quietly break the k/n fairness guarantee:
IndexErrorThis crashes (or silently breaks fairness) once a ban lands early in the stream. Fix it so position is counted only over items that survive the filter.
Quick practice
import random
rng = random.Random(3)
print(rng.randint(0, 4), rng.randint(0, 5))k, n = 3, 10
print(k / n == 3 / 10)🎯 Your turn
Build sample_counts(stream, k, seed, trials): run reservoir_sample
trials times, reseeding deterministically each time, and return a dict
mapping each stream item to how many trials it survived into the final
reservoir.
sample_counts(["a", "b", "c", "d", "e"], 2, seed=7, trials=1000)should give every item a count near1000 * 2 / 5 = 400.
Hint: seed each trial with something that changes every time but stays
deterministic, like seed * 1000 + trial_index. reservoir_sample itself is
the standard Algorithm R from above.
Press ▶ Run, try the Live App chips, then ✓ Check.