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.

Continuous random search methods with an average complexity given by O(log(1/ε)) for ε → 0 where ε is a given accuracy were presented in a recent paper. In this article an example of an O(log log(1/ε)) method is presented and illustrated.

We give an upper bound for the average complexity (i.e. the expected number of steps until termination) for a continuous random search algorithm using results from renewal theory. It is thus possible to show that for a predefined accuracy ε, the average complexity of the algorithm is O(–log ε) for ε → 0 which is optimal up to a constant factor.