Universal Perfect Samplers for Incremental Streams
Seth Pettie, Dingyu Wang · Society for Industrial and Applied Mathematics eBooks · 2025
Given G : ℝ+ → ℝ+, the G-moment of a vector x ∈ ℝ+n is and the G-sampling problem is to select an index v* ∈ [n] according to its contribution to the G-moment, i.e., such that ℙ(v * = v) = G (x(v ))/G (x). Approximate G -samplers may introduce multiplicative and/or additive errors to this probability, and some have a non-trivial probability of failure.