FA-73159 / Probabilistic sketches / Member archive

Reservoir sampling (Algorithm R) with supplied draws: accepted item evicts the oldest slot · case 04

The reservoir behaves like a FIFO window, over-representing recent items.

Member previewVariant 4 · 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	`["e6", "e8", "e11"]`	`["e8", "e4", "e11"]`	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.