FA-73148 / Probabilistic sketches / Member archive

Reservoir sampling (Algorithm R) with supplied draws: replacement range excludes the current item · case 03

Later items are over-sampled because the acceptance probability is k/i instead of k/(i+1).

Member previewVariant 3 · 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	`["e0", "e11", "e7"]`	`["e11", "e3", "e2"]`	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.