Simple Monte Carlo and the metropolis algorithm
Loading...
Date
2006
Authors
Volume
1182
Issue
Journal
Series Titel
WIAS Preprints
Book Title
Publisher
Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik
Link to publishers version
Abstract
We study the integration of functions with respect to an unknown density. Information is available as oracle calls to the integrand and to the non-normalized density function. We are interested in analyzing the integration error of optimal algorithms (or the complexity of the problem) with emphasis on the variability of the weight function. For a corresponding large class of problem instances we show that the complexity grows linearly in the variability, and the simple Monte Carlo method provides an almost optimal algorithm. Under additional geometric restrictions (mainly log-concavity) for the density functions, we establish that a suitable adaptive local Metropolis algorithm is almost optimal and outperforms any non-adaptive algorithm.
Description
Keywords
Citation
Mathé, P., & Novak, E. (2006). Simple Monte Carlo and the metropolis algorithm. Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik.
Collections
License
Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties.
This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties.