FA-73180 / Probabilistic sketches / Member archive

Weighted reservoir sampling by exponential keys: negative weights enter the sample · case 05

An item with negative weight gets a key above every legitimate item and is always sampled.

Member previewVariant 5 · 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
zero and negative weights	`[2, 4, 3]`	`[4, 3]`	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.