FA-73168 / Probabilistic sketches / Member archive

Weighted reservoir sampling by exponential keys: key raises u to the weight · case 03

Heavier items receive smaller keys and are sampled less often than light ones.

Member previewVariant 3 · 3 implementations · 7 checks per implementation

Case contract

Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.

Why this case matters

Weighted sampling without replacement (A-Res) chooses representative traces or accounts in proportion to traffic; key or eligibility mistakes skew the sample.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
weighted sample 0 k=2	`[3, 7]`	`[3, 4]`	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.