THE FOLD / RESPAWN / SECOND WIND / THE RESERVOIR
THE RESERVOIR
a uniform sample from a stream of unknown length, O(1) memory
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Reservoir sampling draws a uniform random sample from a stream of unknown length using O(1) memory — you never store the stream, and you never need to know how many items are coming. For a single-item reservoir (Algorithm R): keep the first item; when the i-th item (0-indexed) arrives, replace the kept item with probability 1/(i+1). When the stream ends, every item was equally likely to be the survivor: probability exactly 1/n.
It is how you sample one random line from a huge log, or a fair winner from an endless feed, in a single pass.
LIT verified live: over 100000 trials on a length-8 stream, each position is selected with empirical frequency within ~2% of 1/8 (window.__reservoir). FIG no framing; the arithmetic makes it exactly uniform.
It is how you sample one random line from a huge log, or a fair winner from an endless feed, in a single pass.
LIT verified live: over 100000 trials on a length-8 stream, each position is selected with empirical frequency within ~2% of 1/8 (window.__reservoir). FIG no framing; the arithmetic makes it exactly uniform.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at second-wind — from an endless stream you can’t hold, one survivor is kept, fairly, and carried on. Reservoir sampling is that fair survivor. AVAN (AI) built the instrument: the 1/(i+1) acceptance rule, the frequency histogram, the uniformity check.
Credit as content: Alan Waterman’s Algorithm R (popularised by Knuth, TAOCP vol. 2; Vitter 1985 for the general k). The weave: David names the survivor; I let the decreasing acceptance probability conspire into exact uniformity, and measure it over 100000 runs.
Credit as content: Alan Waterman’s Algorithm R (popularised by Knuth, TAOCP vol. 2; Vitter 1985 for the general k). The weave: David names the survivor; I let the decreasing acceptance probability conspire into exact uniformity, and measure it over 100000 runs.
3 ONE DIMENSION
As the stream flows, the acceptance probability for the newest item is 1/(i+1): 1, 1/2, 1/3, 1/4… The shrinking chance of being chosen now exactly cancels the growing number of future chances to be replaced.
4 TWO DIMENSIONS · INTERACTIVE
Run many single-item reservoir passes over a length-n stream and watch the selection histogram flatten toward the uniform line 1/n.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the single uniformly-fair survivor of the stream.
AVAN’s addition (the inverse-companion): you never need to know n in advance. The decreasing acceptance probability 1/i exactly cancels the growing chance of later replacement, so every element ends with probability 1/n no matter when the stream stops. The inverse of ‘pick uniformly from a known set’ is ‘accept the i-th with probability 1/i and let the arithmetic conspire to uniformity.’ Magenta is the stream you cannot hold in memory; green is the one survivor, provably fair. Fairness without storage, decided online.
LIT Genuine reservoir sampling, Algorithm R (Waterman/Knuth; Vitter 1985). Verified live: size-1 reservoir over a length-8 stream selects each position with max relative deviation from 1/n of ~0.016 (< 0.05) across 100000 trials (window.__reservoir.uniform).
FIG No framing: the 1/(i+1) acceptance rule and the frequency histogram run in-browser; the empirical distribution is flat to within sampling noise. The AVAN inverse is honest — the decreasing acceptance probability exactly cancels the growing chance of later replacement, so no advance knowledge of n is needed; magenta is the unstorable stream, green the one provably-fair survivor.
FIG No framing: the 1/(i+1) acceptance rule and the frequency histogram run in-browser; the empirical distribution is flat to within sampling noise. The AVAN inverse is honest — the decreasing acceptance probability exactly cancels the growing chance of later replacement, so no advance knowledge of n is needed; magenta is the unstorable stream, green the one provably-fair survivor.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN