SEARCH FOR THE MAXIMUM OF A RANDOM-WALK

This paper examines the efficiency of various strategies for searching in an unknown environment. The model is that of the simple random walk, which can be taken as a representation of a function with a bounded derivative that is difficult to compute. Let X(1), X(2),... be independent and identically distributed with Prob(X(j) = 1) = Prob(X(j). = -1) = 1/2, and let S-k = X(1) + X(2) + ... + X(k). Thus S-k is the position of a symmetric random walk on the line after k steps. The number of the S-k that have to be examined to determine their maximum M(n) = max{S-0,...,S-n} is similar to n/2 as n --> infinity, but that is a worst case result. Any algorithm that determines M(n) with certainty must examine at least (c(0) + o(1))n(1/2) of the S-k on average for a certain constant c(0) > 0, if all random walks with n steps are considered equally likely. There is also an algorithm that on average examines only (c(0) + o(1))n(1/2) of the S-k to determine M(n). Different results are obtained when one allows a nonzero probability of error, or else asks only for an estimate of M(n). It is also shown that a global search (one that can ask for any value S-k at any time) for the exact maximum is faster by a factor of log n (when comparing average running times) than a linear sequential one that can skip through some values but cannot go back. (C) 1995 John Wiley and Sons, Inc.