An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)

Reference: Dagum, P.; Karp, R.; Luby, M.; & Ross, S. An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract). Knowledge Systems Laboratory, Medical Computer Science, September, 1995.

Abstract: 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 it is distributed in $[0,1]$. We describe an approximation algorithm AA which given $\epsilon$ and $\delta$, 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.

Jump to... [KSL] [SMI] [Reports by Author] [Reports by KSL Number] [Reports by Year]
Send mail to: ksl-info@ksl.stanford.edu to send a message to the maintainer of the KSL Reports.