sketch_reservoir.nx

sketch_reservoir.nx -- Vitter reservoir sampling + quantile. Vitter 1985 "Random Sampling with a Reservoir." Algorithm R: maintain a cap-element reservoir. For the i-th input value (1-indexed): - if i <= cap: items[i-1] = value - else: draw j uniformly from [1, i]; if j <= cap, items[j-1] = value (else discard) At end of stream, items[] holds a UNIFORMLY RANDOM sample of the input. Per-quantile estimation: sort items, look up the floor(p * n_items)-th value. Hoeffding bound on quantile from k samples: error ~ sqrt(ln(1/delta) / (2k)) ~ 1/sqrt(k) at fixed delta. We declare 1/sqrt(cap) as the rank_error envelope. OPENS TWO ROADMAP AXES SIMULTANEOUSLY: - Sampling family (Vitter / VarOpt -- DataSketches ships both; this is the first axis primitive) - Quantile family (rank_error envelope; T-Digest / KLL ship this same family with tighter bounds; reservoir is the SIMPLEST sample-based quantile) LCG-based PRNG for deterministic reproducibility. Per the lossless-language discipline (doc 20): randomized sketches MUST declare their RNG state in the typed envelope so two runs with the same seed produce bit-identical output.