A Bayesian Analysis of Randomized Approximation Procedures

From Tetherless World Wiki

Jump to: navigation, search

Citation: Paul Dagum and Eric Horvitz. (1991) A Bayesian Analysis of Randomized Approximation Procedures. In , September,1991.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Paul Dagum and Eric Horvitz
title A Bayesian Analysis of Randomized Approximation Procedures
number KSL-91-54
institution Knowledge Systems, AI Laboratory
address Stanford, CA, USA
year 1991
month September
Bibtex more
Access Paper
abstract Computer scientists have used Zero-One Estimation Theory to develop a body of results on the convergence of Monte-Carlo algorithms. In much of this work, investigators have analyzed bounds on the variance of an estimator p after N trials assuming knowledge of the expectation u of a random variable. We present an alternative framework for analyzing randomized approximation procedures that considers the manner in which u are distributed for Bernoulli processes. Rather than relying on results about error that follow from the assumption of independent and identically distributed random variables, we consider the properties of the beta distribution. The beta is a conjugate distribution for the Bernoulli sampling processes. Conjugate distributions allow us to represent both the prior and posterior probability distributions for a sampling process. We derive probabilistic stopping rules for Monte-Carlo algorithms by approximating the portion of the cumulative distribution of the beta defined by bounds on error. The probabilistic stopping rules do not require prior knowledge or estimates of u. We prove an upper bound on N that is a function of the value of the estimator p rather than u. For small relative error or u, our stopping rule gives an O(log n) speed-up on the running time of Monte-Carlo algorithms over the running time predicted by the Zero-One Estimator Theorem.

KSL Technical Report ID: KSL-91-54
Facts about A Bayesian Analysis of Randomized Approximation ProceduresRDF feed
Abstract Computer scientists have used Zero-One Est … Computer scientists have used Zero-One Estimation Theory to develop a body of results on the convergence of Monte-Carlo algorithms. In much of this work, investigators have analyzed bounds on the variance of an estimator p after N trials assuming knowledge of the expectation u of a random variable. We present an alternative framework for analyzing randomized approximation procedures that considers the manner in which u are distributed for Bernoulli processes. Rather than relying on results about error that follow from the assumption of independent and identically distributed random variables, we consider the properties of the beta distribution. The beta is a conjugate distribution for the Bernoulli sampling processes. Conjugate distributions allow us to represent both the prior and posterior probability distributions for a sampling process. We derive probabilistic stopping rules for Monte-Carlo algorithms by approximating the portion of the cumulative distribution of the beta defined by bounds on error. The probabilistic stopping rules do not require prior knowledge or estimates of u. We prove an upper bound on N that is a function of the value of the estimator p rather than u. For small relative error or u, our stopping rule gives an O(log n) speed-up on the running time of Monte-Carlo algorithms over the running time predicted by the Zero-One Estimator Theorem. edicted by the Zero-One Estimator Theorem.
Address Stanford, CA, USA  +
Author Paul Dagum and Eric Horvitz  +
Bibtype techreport  +
Has author Paul Dagum and Eric Horvitz  +
Has identifier KSL-91-54  +
Has publishing details September,1991  +
Has title A Bayesian Analysis of Randomized Approximation Procedures  +
Has year 1991  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-91-54  +
Month September  +
Number KSL-91-54  +
Process note NO  +
Title A Bayesian Analysis of Randomized Approximation Procedures  +
Year 1991  +
Retrieved from "http://tw.rpi.edu/wiki/A_Bayesian_Analysis_of_Randomized_Approximation_Procedures"
Personal tools