Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-12T19:43:49.164Z Has data issue: false hasContentIssue false
  • English
  • Français

Average case behavior of random search for the maximum

Part of: Theory of computing Markov processes

Published online by Cambridge University Press:  14 July 2016

James M. Calvin  and
Peter W. Glynn
James M. Calvin*
Affiliation:
New Jersey Institute of Technology
Peter W. Glynn*
Affiliation:
Stanford University
*
∗Postal address: Department of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ 07102-1982, USA.
∗∗Postal address: Department of Operations Research, Stanford University, Stanford, CA 94305-4022, USA.
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

BROWNIAN MOTIONGLOBAL OPTIMIZATIONAVERAGE COMPLEXITY

MSC classification

Primary: 60J65: Brownian motion
Secondary: 68Q25: Analysis of algorithms and problem complexity
Type
Research Papers
Information
Journal of Applied Probability , Volume 34 , Issue 3 , September 1997 , pp. 632 - 642
Copyright
Copyright © Applied Probability Trust 1997 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

The research of JMC is supported by the National Science Foundation under grant DDM-9010770.

The research of PWG is supported by the National Science Foundation under grant DDM-9101580 and the Army Research Office under Contract No. DAAL03-91-G-0319.

References

Al-Mharmah, H. and Calvin, J. (1996) Optimal random non-adaptive algorithm for global optimization of Brownian motion. J. Global Opt. 8, 81–90.CrossRefGoogle Scholar
Asmussen, S., Glynn, P. and Pitman, J. (1994) Discretization error in simulation of one-dimensional reflecting Brownian motion. Technical Report 94-1. Stanford University.Google Scholar
Calvin, J. (1995) Average performance of non-adaptive algorithms for global optimization of Brownian motion. J. Math. Anal. Appl. 191, 608–617.Google Scholar
De Haan, L. (1981) Estimation of the minimum of a function using order statistics. J. Amer. Statist. Assoc. 76, 467–469.CrossRefGoogle Scholar
Fitzsimmons, P. J. (1985) Excursions above the minimum for diffusions. Unpublished manuscript. Google Scholar
Fitzsimmons, P. J., Pitman, J. W. and Yor, M. (1992) Markovian bridges: construction, Palm interpretation, and splicing. In Sem. Stochastic Processes 1992. Birkhäuser, Boston.Google Scholar
Leadbetter, M., Lindgren, G. and Rootzen, H. (1983) Extremes. Springer, New York.Google Scholar
Revuz, D. and Yor, M. (1991) Continuous Martingales and Brownian Motion. Springer, Berlin.Google Scholar
Ritter, K. (1990) Approximation and optimization on the Wiener space. J. Complexity 6, 337–364.CrossRefGoogle Scholar
Salminen, P. (1983) Brownian excursions revisited. In Sem. Stochastic Processes 1983. ed. Çinlar, E., Chung, K. L. and Getoor, R. K. Birkhäuser, Boston.Google Scholar
Williams, D. (1974) Path decomposition and continuity of local time for one-dimensional diffusions, I. Proc. London Math. Soc. 28, 738–768.Google Scholar
Zhigljavsky, A. (1991) Theory of Global Random Search. Kluwer, Dordrecht.Google Scholar