AVERAGE-CASE BEHAVIOR OF RANDOM SEARCH FOR THE MAXIMUM

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 r andomly 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 f irst case we show that for almost all Brownian paths the error, normal ized by multiplying by the square root of the number of observations, does not converge in distribution, while in the second case the normal ized error does converge in distribution. We derive the limiting distr ibution of the normalized error averaged over all paths.