An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)

From Tetherless World Wiki

Jump to: navigation, search

Citation: Paul Dagum and Richard M. Karp and Michael Luby and Sheldon M. Ross. (1995) An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract). In KSL-95-73, September,1995.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Paul Dagum and Richard M. Karp and Michael Luby and Sheldon M. Ross
title An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)
number KSL-95-73
institution Knowledge Systems, AI Laboratory
address Stanford, CA, USA
year 1995
month September
Bibtex more
note Medical Computer Science
Access Paper
abstract [[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.|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.]]

KSL Technical Report ID: KSL-95-73
Facts about An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)RDF feed
Address Stanford, CA, USA  +
Author Paul Dagum and Richard M. Karp and Michael Luby and Sheldon M. Ross  +
Bibtype techreport  +
Has author Paul Dagum and Richard M. Karp and Michael Luby and Sheldon M. Ross  +
Has identifier KSL-95-73  +
Has publishing details September,1995  +
Has title An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)  +
Has where published KSL-95-73  +
Has year 1995  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-95-73  +
Month September  +
Note Medical Computer Science
Number KSL-95-73  +
Process note NO  +
Title An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)  +
Year 1995  +
Retrieved from "http://tw.rpi.edu/wiki/An_Optimal_Algorithm_for_Monte_Carlo_Estimation_%28Extended_Abstract%29"
Personal tools