KSL-95-73
## 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.