caa a22 4500 445869615 CHVBK 20180317145507.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00236-011-0145-8 doi (NATIONALLICENCE)springer-10.1007/s00236-011-0145-8 The query complexity of estimating weighted averages [Elektronische Daten] [Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth] The query complexity of estimating the mean of some [0, 1] variables is understood. Inspired by some work by Carterette etal. 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 $${\varepsilon}$$ , with high probability, requires $${\Omega(\varepsilon^{-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 $${\Omega(\log (1/\varepsilon))}$$ suffices. Our principal contribution is the investigation of power-law sequences of weights. We show that if the ith largest weight is proportional to i −p , for p > 1, then the query complexity is in $${\Omega(\varepsilon^{2/(1-2p)})}$$ . Springer-Verlag, 2011 Chakrabarti Amit Department of Computer Science, Dartmouth College, 03755, Hanover, NH, USA aut Guruswami Venkatesan Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut Wirth Andrew Department of Mechanical Engineering, The University of Melbourne, 3010, Parkville, VIC, Australia aut Wirth Anthony Department of Computer Science and Software Engineering, The University of Melbourne, 3010, Parkville, VIC, Australia aut Acta Informatica Springer-Verlag 48/7-8(2011-12-01), 417-426 0001-5903 48:7-8<417 2011 48 236 https://doi.org/10.1007/s00236-011-0145-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00236-011-0145-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chakrabarti Amit Department of Computer Science, Dartmouth College, 03755, Hanover, NH, USA aut NATIONALLICENCE 700 1- Guruswami Venkatesan Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 700 1- Wirth Andrew Department of Mechanical Engineering, The University of Melbourne, 3010, Parkville, VIC, Australia aut NATIONALLICENCE 700 1- Wirth Anthony Department of Computer Science and Software Engineering, The University of Melbourne, 3010, Parkville, VIC, Australia aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 48/7-8(2011-12-01), 417-426 0001-5903 48:7-8<417 2011 48 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer