The query complexity of estimating weighted averages

Abstract

The query complexity of estimating the mean of some [0, 1] variables is understood. Inspired by some work by Carterette et al. on evaluating retrieval systems, and by Moffat and Zobel's new proposal for such evaluation, we examine the query complexity of weighted average calculation. In general, determining an answer within accuracy e{open}, with high probability, requires Ω(e{open}-2) queries, as the mean is a special case. There is a matching upper bound for the weighted mean. If the weights are a normalized prefix of a divergent series, the same result holds. However, if the weights follow a geometric sequence, a sample of size Ω(log(1/e{open})) suffices. Our principal contribution is the..