Adaptive approximation of the minimum of Brownian motion

James M. Calvin, Mario Hefter, André Herzwurm

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We study the error in approximating the minimum of a Brownian motion on the unit interval based on finitely many point evaluations. We construct an algorithm that adaptively chooses the points at which to evaluate the Brownian path. In contrast to the 1/2 convergence rate of optimal nonadaptive algorithms, the proposed adaptive algorithm converges at an arbitrarily high polynomial rate.

Original languageEnglish (US)
Pages (from-to)17-37
Number of pages21
JournalJournal of Complexity
Volume39
DOIs
StatePublished - Apr 1 2017

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics(all)
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Adaptive algorithm
  • Brownian motion
  • Global optimization
  • Pathwise approximation

Fingerprint

Dive into the research topics of 'Adaptive approximation of the minimum of Brownian motion'. Together they form a unique fingerprint.

Cite this