Fast averaging

We are interested in the following question: given n numbers x₁, ..., x_n, what sorts of approximation of average x_ave = 1overn (x₁ + ... + x_n) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation in these n numbers. As the main result, we show that if the vector of these n numbers satisfies certain regularity properties captured in the form of finiteness of their empirical moments (third or higher), then it is possible to compute approximation of x_ave that is within 1 ±ε multiplicative factor with probability at least 1 - δ by choosing, on an average, r = r(ε, δ, σ) of the n numbers at random with r is dependent only on ε, δ and the amount of variation σ in the vector and is independent of n. The task of computing average has a variety of applications such as distributed estimation and optimization, a model for reaching consensus and computing symmetric functions. We discuss implications of the result in the context of two applications: load-balancing in a computational facility running MapReduce, and fast distributed averaging.