Estimating Sum by Weighted Sampling
- Rajeev Motwani ,
- Rina Panigrahy ,
- Ying Xu 0002
International Colloquium on Automata, Languages and Programming, (ICALP) |
We study the classic problem of estimating the sum of n variables. The traditional uniform sampling approach requires a linear number of samples to provide any non-trivial guarantees on the estimated sum. In this paper we consider various sampling methods besides uniform sampling, in particular sampling a variable with probability proportional to its value, referred to as linear weighted sampling. If only linear weighted sampling is allowed, we show an algorithm for estimating sum with