An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)
A typical approach to estimate an unknown quantity p is to design an experiment that produces a random variable Z distributed in [0,1] with E[Z] = p, 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 Ad which, given E and 6, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+~ of p with probability at least 1 - 6. We prove that the expected number of experiments run by AA which depends on Z) is optimal to within a constant J actor for every Z.