Even Odds

You are handed items one at a time. You may keep k of them. You are not told how many are coming, you cannot go back, and when it stops you must have a uniformly random sample of everything you saw.

The rule that does this is four lines long and looks obviously broken:

for item i:
  if i <= k:            take it
  else with prob k/i:   overwrite a slot chosen uniformly at random

Item 1 is taken for certain. Item 1,000,000 is taken at odds of five in a million. Two items whose treatment differs by a factor of 200,000 are supposed to end up equally likely to be in the answer, and the only honest way to believe that is to run whole passes and count.

Why the unfairness cancels

Being in the final sample takes two things: getting in, and not being thrown out again. Item i gets in with probability k/i. Once in, it survives item j unless j is admitted and picks its slot — probability (k/j)·(1/k) = 1/j. So it survives to the end with

∏ (1 − 1/j) for j = i+1..n   =   ∏ (j−1)/j   =   i/n

which telescopes, and

P(item i in the sample) = (k/i) · (i/n) = k/n

The i cancels. (That is the argument for i > k. The first k are taken outright, and the same product run from k+1 leaves them at k/n too, so there is no special case — only a shorter derivation.)

The decaying coin is not an approximation of fairness; it is the exact inverse of how long an item still has to survive. Item 1 is certain to be taken and almost certain to be evicted. The last item is almost never taken and, if taken, certain to survive. These are the same statement.

Is it flat?

The only test that means anything: run 20,000 complete passes of n = 240 with k = 5 and count how often each position ends up in the sample. Target k/n = 0.02083; a rate measured over 20,000 passes carries a 3σ band of ±0.00303, so “flat” means no position wanders much past that.

One position of 240 outside a 3σ band is what 240 positions should produce. R and L are flat to the precision 20,000 passes can resolve, and they are flat for the same reason: L is R, with the arithmetic done in advance.

Where the sample comes from, by eighths of the stream, as a multiple of k/n:

The two rivals worth looking at

Replace at 1/2 is the instructive failure, because it is the rule you get by remembering that reservoir sampling involves a coin and forgetting which coin. A fixed probability means an item’s survival odds halve with every item behind it, so the sample is a geometric smear on the tail: the last item is in it 50.2% of the time against a correct 2.1%, and the last tenth of the stream supplies 92.1% of the answer. It is not a sample. It is a recency list that costs more than one.

Guess n̂ first is the interesting one, because it is not biased at all. Admit every item independently at k/n̂ and you are perfectly uniform — 0 of 240 positions outside the band, flatter in this run than R itself. It just doesn’t return k items:

Guess the length of the stream perfectly and you still get the size you asked for 17.7% of the time, and nothing at all once in 139 runs. Guess 2× high and one run in twelve returns an empty sample. Bias is not the only way to be wrong, and a fixed-size reservoir is not a detail of the implementation — it is half of what the algorithm is for.

What a pass costs

Writes are a sum of Bernoulli(k/i), which is a harmonic sum, so the expected total is k(1 + Hₙ − Hₖ) and grows like log n. Measured against that closed form, k = 5, whole passes:

Over a million items the reservoir is written about 66 times — 0.0064% of the stream. And half of those writes happen before item 1,458, the first 0.14%, because writes are uniform in log i, not in i. Almost all of the writing happens at the beginning. None of the bias does: the five survivors sit spread evenly across the full width while the record of every write piles into the left edge, which is the picture the stream view exists to show.

But R still throws a coin at every item it declines. The work is logarithmic and the randomness is linear, and only one of those two is forced:

n = 1,048,576, k = 5
R:  one coin per item                     1,048,633 coins
L:  sample the gap to the next write            185 coins

Algorithm L keeps the k-th largest key as W and draws a geometric jump straight to the next item that will win, so it never looks at the 9,951 items out of 10,000 it was going to reject anyway. Same distribution, 5,684× fewer random numbers. That ratio is the whole argument for L, and it is the only thing in this subject that is a pure win — up to a point. At k = 25, n = 64 the ladder crosses the other way: 62 coins for R against 72 for L, because L pays three draws per write and at that k almost everything is a write.

Items that aren’t equal

If items carry weights, the one-pass answer is the exponential race: give item i the key log(u)/wᵢ and keep the k largest. No n, one pass, any positive weights. This is A-Res (Efraimidis–Spirakis), and it is universally described as giving inclusion probability proportional to weight.

It does, at k = 1. Over 400,000 passes, four weight shapes, 24 items, the worst position in each lands 0.92 / 0.72 / 0.77 / 1.55 × its 3σ band — exact, for any weights at all, which is just the race: P(item i is fastest) = wᵢ/Σw.

Above k = 1 it is not proportional, and the error is not noise. Weights ramped 1 → 10 across 24 items, 200,000 passes each, nothing saturated (every target below 1):

A-Res compresses toward the middle, and it compresses in the direction that hurts: the items you deliberately weighted up are the ones it under-samples. At k = 12 the heaviest item shows up 17% less often than the proportional reading promises, 47σ away from it, with nothing clipped and nothing degenerate about the weights.

The mechanism is visible once you notice that the measured probabilities sum to exactly k — they must, because the sample is always size k. Successive sampling without replacement cannot hand an item more than 1, and more generally cannot spend more than k in total, so every point of probability a heavy item is unable to absorb gets pushed down onto the light ones. With one whale (one item at weight 40 against 23 at weight 1) and k = 4, the whale wants 1.000 and gets 0.985 — and each light item, asking for 0.064, gets 0.132, more than double. The excess has to land somewhere.

This matters whenever the weights are the point: weighted sampling for telemetry, importance sampling, or anything where a heavy key is heavy because you need to see it. If you need true πᵢ ∝ wᵢ at k > 1, A-Res is not it — that is a different algorithm (conditional Poisson / Sampford), and it is not one pass.

Reading it

Four views, 1 2 3 4. space plays and pauses, r restarts the pass, [ and ] step k.

• stream — one live pass. The reservoir on top, the gate in the middle with the admit zone shrinking as k/i decays and the coin landing in or out of it, and the stream at the bottom: a faint mark for every write, a white mark for every item still held. The writes crowd the left edge; the survivors don’t. Switch rule to watch a wrong one fail live — keep the last k never stops writing, guess n̂ overflows or starves, Algorithm L skips thousands of items without reading them.
• flat? — the measurement above, as six panels. This is the view that decides anything.
• cost — writes and coins against stream length, log on both axes, measured points over the closed form.
• weighted — A-Res inclusion against k·w/Σw. Bars are measured, white ticks are the proportional reading; blue means above it, red below. Set k = 1 and they agree; raise k and watch the tail lift.

Reuse

src/even-odds.js is a framework-free ES module. No DOM, no timers, no rendering.

• createRun({n, k, policy, seed, guessFactor}) → a stepping pass. .step() returns {i, kind, slot, evicted, p, u} where kind is fill / write / reject / skip / over. Also .sample, .slots, .overwrites, .admitted, .writes, .draws, .skips, .admitProb(i).
• POLICIES / POLICY_ORDER — r, l, first, last, coin, guess.
• inclusion({n, k, policy, runs}) → per-position rates, the k/n target, the 3σ band, and the sample-size distribution. binned(prob, bins) collapses it.
• costLadder({k, ns, budget}) → writes and draws per n for R and L, beside the closed forms.
• weightedSample({w, k, seed}) → A-Res in log space over a k-sized min-heap. weightedInclusion({shape, n, k, runs}) → measured vs. proportional. WEIGHT_SHAPES / weights(shape, n).
• expectedWrites(n, k), expectedDrawsR/L(n, k), halfWriteIndex(n, k), harmonic(n) — the closed forms, so a claim can be checked against a counter.
• rng(seed), fmtCount, pct.

Items are their own payload — item i is i — so a reservoir is a list of stream positions and a sample is a set of indices. That is what makes the inclusion histogram possible at all: there is nothing to compare but position.

Gotchas

• “Flat” is a statement about a band, not a line. Every claim of uniformity here is “no position strayed past 3σ for this many passes.” Push runs up and the band tightens; push it far enough and real implementations start to show their PRNG. This one is mulberry32, and at 20,000 passes it is nowhere near the limiting factor.
• A-Res is exact only at k = 1. The weighted view defaults to a k where the deviation is already visible. If you cite “proportional to weight” from the paper, cite the k = 1 case; above it the measured answer is the successive-sampling one, not the proportional one.
• The cap is not the whole story. It is tempting to explain the weighted error as “probabilities can’t exceed 1.” The ramp table has nothing capped and deviates by 47σ anyway.
• L’s win is in random numbers, not in items touched. If your stream arrives over a socket you still read every byte; what you skip is the coin and the branch. L pays off for an in-memory array or an mmap’d file, and when k is a large fraction of n it costs more than R.
• Draws are counted, not timed. A coin from mulberry32 and a log() are billed the same here, and L spends three draws and two logarithms per write against R’s one draw per item. At k/n near 1 that is the crossing above; the shape of the two curves is robust, the exact crossing point is not.
• guess n̂ keeps everything it admits. Truncating it to the first k admitted would fix the size and reintroduce the head bias of keep the first k — which is the trap, and why it is drawn with an over-budget slot rather than silently clipped.
• n = 240 for the flat view so 20,000 passes stay interactive. The flatness result does not depend on it; the band does, and the view recomputes runs so n·runs stays bounded.
• The last-item probability under replace at 1/2 is exactly 1/2 and the measurement says 0.5019. If you want a one-line check that the harness is billing honestly, that is the one with a closed form you can do in your head.
• The demo bundles its own copy of even-odds.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--view=stream|flat|cost|weighted] [--policy=] [--k=] [--n=] [--runs=] [--guess=] [--shape=] [--items=] [--w= --h=] regenerates thumb.png and media/ through site/scripts/lib/chromium.mjs, consuming a fixed number of items so a capture of the live view is reproducible.