# DIMACS Theory of Computing Seminar

## Title:

An Optimal Algorithm for Monte Carlo Estimation

## Speaker:

- Michael Luby
- International Computer Sciences Institute

## Place:

- DIMACS Seminar Room 431, CoRE Building
- Busch Campus, Rutgers University

## Time:

- 4:30 PM
- Tuesday, October 17, 1995 (Note Day Change: this replaces the Discrete Math Seminar for the week)

## Abstract:

A typical approach to estimate an unknown quantity M is to design an experiment
that produces a random variable Z whose expected value is M and
run this experiment independently a number of times and use the average
of the outcomes as the estimate. The goal is to produce a good
relative estimate of M with high probability.
Usually $Z$ is distributed in the interval [0,1],
or can be renormalized so that this is the case.
We describe an approximation algorithm A which,
given small parameters c and d, runs independent experiments
and produces an estimate that is within a factor 1+c
of M with probability at least 1-d. The number
of experiments run by A is proportional to quantities
that depend on the distribution Z, which are unknown
a priori. We prove that the expected number of experiments
run by A is optimal to within a constant factor for every Z.

There are a number of applications where Monte Carlo algorithm
simulation of the type suggested above has been used and where
the analysis of the number of experiments to run is far from
tight for every problem instance. The algorithm A can be directly used
in these applications to produce a provably good estimate
while running the minimal number of experiments needed for the
particular problem instance.

JOINT WORK WITH: Paul Dagum, Richard Karp, and Sheldon Ross

dimacs-www@dimacs.rutgers.edu
Document last modified on October 11, 1995