An optimal algorithm for monte carlo estimation (extended abstract)

From Semantic Portal Wiki

{{#vardefine:category|Publication}}{{#vardefine:templatename|i.publication}}{{#vardefine:package|smwbp_instance_templates}}

Edit

[[abstract::A typical approach to estimate an unknown quantity $\mu$ is to designan experiment that produces a random variable $Z$ distributed in$[0,1]$ with $E[Z]=\mu$, run this experiment independently a number oftimes and use the average of the outcomes as the estimate. In thispaper, we consider the case when no a priori information about $Z$ isknown except that it is distributed in $[0,1]$. We describe anapproximation algorithm AA which given $\epsilon$ and $\delta$, when runningindependent experiments with respect to any Z, produces an estimatethat is within a factor $1+\epsilon$ of $\mu$ with probability at least$1-\delta$. We prove that the expected number of experiments run byAA (which depends on Z) is optimal to within a constant factor for everyZ.|]]

Reference: {{#vardefine:pagename|an optimal algorithm for monte carlo estimation (extended abstract) }}

1. [[]]

bibtex

{{#vardefine:pagename|An optimal algorithm for monte carlo estimation (extended abstract) }}{{#vardefine:key| }}

abstract: A typical approach to estimate an unknown quantity $\mu$ is to designan experiment that produces a random variable $Z$ distributed in$[0,1]$ with $E[Z]=\mu$, run this experiment independently a number oftimes and use the average of the outcomes as the estimate. In thispaper, we consider the case when no a priori information about $Z$ isknown except that it is distributed in $[0,1]$. We describe anapproximation algorithm AA which given $\epsilon$ and $\delta$, when runningindependent experiments with respect to any Z, produces an estimatethat is within a factor $1+\epsilon$ of $\mu$ with probability at least$1-\delta$. We prove that the expected number of experiments run byAA (which depends on Z) is optimal to within a constant factor for everyZ.

download:

• paper:
• slides: