FA-73165 / Probabilistic sketches / Member archive

Reservoir sampling (Algorithm R) with supplied draws: draw tape advanced only on replacement · case 05

Rejected items do not consume randomness, so later decisions reuse the same draw.

Member previewVariant 5 · 3 implementations · 7 checks per implementation

Case contract

Input {k, items, draws}. The first k items fill the reservoir. For 0-based index i >= k the draw draws[i - k] gives j = draw mod (i + 1); when j < k slot j is replaced. Exactly one draw is consumed per item after the fill phase. Return the reservoir.

Why this case matters

Uniform stream samples feed audit logs and A/B diagnostics; any skew in the replacement rule biases the sample toward early or late events.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
reservoir 0 k=3	`["e7", "e1", "e9"]`	`["e4", "e1", "e5"]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.