Average case behavior of random search for the maximum

James M. Calvin, Peter W. Glynn

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

This paper is a study of the error in approximating the global maximum of a Brownian motion on the unit interval by observing the value at randomly chosen points. One point of view is to look at the error from random sampling for a given fixed Brownian sample path; another is to look at the error with both the path and observations random. In the first case we show that for almost all Brownian paths the error, normalized by multiplying by the square root of the number of observations, does not converge in distribution, while in the second case the normalized error does converge in distribution. We derive the limiting distribution of the normalized error averaged over all paths.

Original languageEnglish (US)
Pages (from-to)632-642
Number of pages11
JournalJournal of Applied Probability
Volume34
Issue number3
DOIs
StatePublished - Sep 1997

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Mathematics(all)
  • Statistics, Probability and Uncertainty

Keywords

  • Average complexity
  • Brownian motion
  • Global optimization

Fingerprint Dive into the research topics of 'Average case behavior of random search for the maximum'. Together they form a unique fingerprint.

Cite this