An optimal algorithm for Monte Carlo estimation

A typical approach to estimate an unknown quantity mu is to design an experiment that produces a random variable Z distributed in [0, 1] with E[Z] = mu, run this experiment independently a number of times, and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [ 0, 1]. We describe an approximation algorithm AA which, given and, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+epsilon of mu with probability at least 1-delta. We prove that the expected number of experiments run by AA (which depends on Z) is optimal to within a constant factor for every Z.