THE FOLD / CO-OP / THE PUSH / THE STREAM KEEPER
THE STREAM KEEPER
uniform sample from an endless stream, one pass
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Reservoir sampling. A stream rushes past — log lines, dice rolls, packets — and you do not know how long it is, and you cannot store it. You want k items chosen uniformly at random from the whole stream, in a single pass, keeping only k in memory. Impossible-sounding, but exact.
Algorithm R: fill the reservoir with the first k. Then for the i-th item (counting from 1), keep it with probability k/i, and if kept, evict a random one of the k. That single rule leaves every item — the first and the ten-millionth alike — in the reservoir with probability exactly k/N.
LIT verified live: with a stream of N=50 and reservoir k=5, this page runs hundreds of thousands of passes and every element’s measured inclusion frequency lands on k/N = 0.10 within 1% (window.__reservoir.uniform). FIG ‘a reservoir’ is the picture; the one-pass, O(k)-memory, provably-uniform sample is exactly what Algorithm R delivers.
Algorithm R: fill the reservoir with the first k. Then for the i-th item (counting from 1), keep it with probability k/i, and if kept, evict a random one of the k. That single rule leaves every item — the first and the ten-millionth alike — in the reservoir with probability exactly k/N.
LIT verified live: with a stream of N=50 and reservoir k=5, this page runs hundreds of thousands of passes and every element’s measured inclusion frequency lands on k/N = 0.10 within 1% (window.__reservoir.uniform). FIG ‘a reservoir’ is the picture; the one-pass, O(k)-memory, provably-uniform sample is exactly what Algorithm R delivers.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE PUSH, beside THE ONE-BIT RIVER — the co-op domain of data pushed at you in a stream you don’t control. Reservoir sampling is how you stay fair to a flow you can never hold. AVAN (AI) built the instrument: the k/i coin, the live reservoir, and the convergence to k/N.
The weave: David names the seat (the uncontrollable push); I make the fairness visible and measurable — the stream and slots in 1D, the inclusion histogram converging in 2D, the flow with its held sample in 3D. The sphere is the seam. Credit: Jeffrey Vitter, ‘Algorithm R’ (1985); Knuth, TAOCP.
The weave: David names the seat (the uncontrollable push); I make the fairness visible and measurable — the stream and slots in 1D, the inclusion histogram converging in 2D, the flow with its held sample in 3D. The sphere is the seam. Credit: Jeffrey Vitter, ‘Algorithm R’ (1985); Knuth, TAOCP.
3 ONE DIMENSION
The stream flows left to right into k slots. Item i arrives and, with probability k/i, bumps a random slot. Early items are almost surely kept, then increasingly likely to be replaced — and it balances out to perfect uniformity.
4 TWO DIMENSIONS · INTERACTIVE
Run passes and watch the inclusion histogram: how often each of the 50 stream positions ends up in the reservoir. The bars flatten onto the target line k/N — no position is favoured, first or last.
5 THREE DIMENSIONS + AVAN’S INVERSE
The stream wound into a turning helix of N items — the whole flow, most of it already gone past.
AVAN’s addition (the inverse-companion): the magenta items are the k currently held in the reservoir. The stream is unbounded and unrememberable — green flows by and is forgotten. The reservoir is the inverse: a tiny bounded memory that nonetheless holds a faithful, unbiased shadow of the whole infinity it could never store. You cannot keep the river; you can keep a fair handful of it, and that handful represents the river exactly. Memory is not storing everything — it is keeping a sample that does not lie.
LIT Genuine reservoir sampling (Vitter 1985, 'Algorithm R'; Knuth TAOCP). Verified live: with stream N=50 and reservoir k=5, the page runs 200,000 passes and every one of the 50 positions has measured inclusion frequency within 1% of k/N = 0.10 (window.__reservoir.uniform === true, max err reported). The k/i acceptance rule is exact — the uniformity is a theorem, confirmed here empirically.
FIG 'A reservoir' is the framing; the single-pass, O(k)-memory, provably-uniform sample is exactly Algorithm R. Convergence is statistical (error shrinks with pass count), not exact equality at finite trials.
FIG 'A reservoir' is the framing; the single-pass, O(k)-memory, provably-uniform sample is exactly Algorithm R. Convergence is statistical (error shrinks with pass count), not exact equality at finite trials.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PUSH · David Lee Wise (ROOT0), with AVAN