UniformSampling is positionally biased: early stream positions survive at 33%, late at 68%

[GordonYuanyc]

Summary

UniformSampling (src/sketches/uniform.rs, experimental feature) does not produce a uniform sample of the stream. Elements that arrive early are systematically under-represented in the retained sample.

Evidence

4000 independent trials, rate = 0.5, 20-element stream, counting how often each stream position survives into the final sample:

position	0	1	2	3	4	5	6	7	8	9
survived	1310	1317	1682	1535	1739	1787	1858	1916	1963	1957

position	10	11	12	13	14	15	16	17	18	19
survived	2023	2050	2089	2095	2305	2229	2408	2386	2631	2720

Monotonically increasing. Position 0 survives 32.75% of the time, position 19 survives 68%. Under uniform sampling at rate 0.5 every position should survive ~50%. Measured skew between the first and last thirds of the stream: 36.2%.

Root cause

update() (uniform.rs:102-108) maintains the retained set as the bottom-k by priority, with k = target_size(n) = ceil(n * rate) recomputed after every insert:

pub fn update(&mut self, value: f64) {
    self.total_seen = self.total_seen.saturating_add(1);
    let target_size = Self::target_size(self.total_seen, self.sample_rate);
    let priority = self.next_random();
    self.insert_entry(SampleEntry::new(priority, value));
    self.truncate_to(target_size);
}

target_size is monotonically non-decreasing, but an evicted element can never come back. So when k later grows, the true bottom-k of the stream-so-far is no longer recoverable — the sketch can only draw from what it still holds.

Concretely at rate = 0.6:

• n=3, k=2: the sketch holds bottom-2 of {e1,e2,e3} and has discarded one element.
• n=4, k=3: the sketch can only offer {bottom-2 of e1..e3} ∪ {e4}. If the discarded element belongs to the true bottom-3 of {e1..e4}, it is unrecoverable.

The result is that survival probability is not uniform across positions: late arrivals face fewer eviction rounds. The bias vanishes at rate = 1.0 (nothing is ever discarded) and grows as the rate decreases.

Reproduction

#[test]
fn uniform_sampling_is_positionally_unbiased() {
    use asap_sketchlib::UniformSampling;

    const STREAM_LEN: usize = 20;
    const TRIALS: usize = 4000;
    const RATE: f64 = 0.5;

    let mut survived = vec![0usize; STREAM_LEN];
    for trial in 0..TRIALS {
        let mut sampler = UniformSampling::with_seed(RATE, 0x1000 + trial as u64);
        for pos in 0..STREAM_LEN {
            sampler.update(pos as f64);
        }
        for v in sampler.samples() {
            survived[v as usize] += 1;
        }
    }

    let third = STREAM_LEN / 3;
    let early: usize = survived[..third].iter().sum();
    let late: usize = survived[STREAM_LEN - third..].iter().sum();
    let early_rate = early as f64 / (third * TRIALS) as f64;
    let late_rate = late as f64 / (third * TRIALS) as f64;
    let skew = (early_rate - late_rate).abs() / late_rate.max(1e-9);

    assert!(
        skew < 0.10,
        "positional bias: early {early_rate:.4} vs late {late_rate:.4} \
         (skew {:.1}%), both should equal {RATE}. counts: {survived:?}",
        skew * 100.0
    );
}

Run with cargo test --features experimental.

Notes

• The existing tests (sample_count_tracks_rate, samples_are_drawn_from_input_stream) only assert the sample size and that values come from the input domain. Neither probes the sampling distribution, which is why this went unnoticed.
• The commit that introduced this, 66759a1, is titled "add uniform sampling with vibe coding: needs revisiting".

Possible directions

Either commit to a fixed-size reservoir (classic Vitter reservoir sampling, unbiased by construction) or keep the rate-proportional size but retain evicted entries until k is known not to grow past them. The current shape — a growing k over a lossy bottom-k — cannot be made unbiased without one of those changes.